题目描述

image.png

代码

思路：使用了栈后进先出的思想。

class Solution {
    public String removeOuterParentheses(String S) {
        StringBuilder sb = new StringBuilder();

        Stack<Character> stack = new Stack<>();
        int start = 0;
        int end = 0;
        boolean flag = false;
        for(int i = 0;i<S.length();i++){
            if(S.charAt(i) == '('){
                stack.push(S.charAt(i));
                if(!flag){
                    start = i;
                    flag = true;
                }
            }

            if(S.charAt(i) == ')'){
                stack.pop();
                if(stack.isEmpty()){
                    end = i;
                    sb.append(S.substring(start+1, end));
                    flag = false;
                    start = end;
                }
            }
        }

        return sb.toString();
    }
}

延伸

给一个字符串a#bc#d#e#f，要求输出两个#号中间的字符串，但是如果前一个字符串使用了该#，后面的就不能使用。所以该字符串输出结果应该是bc e

代码

这里同样使用了栈的思路。该题目类似于微博的话题。

public static List<String> getString(String S) {
        List<String> list = new ArrayList<>();
        Stack<Character> stack = new Stack<>();
        int start = 0;
        int end = 0;

        for (int index = 0; index < S.length(); index++) {
            if (S.charAt(index) == '#') {
                if (stack.isEmpty()) {
                    stack.push(S.charAt(index));
                    start = index;
                } else {
                    stack.pop();
                    end = index;
                    list.add(S.substring(start + 1, end));
                }
            }
        }
        return list;
    }