LeetCode Parentheses 括号处理相关习题

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

LeetCode题目：20. Valid Parentheses 判断括号是否合法
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

class Solution {
    public boolean isValid(String s) {
        char[] arr = s.toCharArray();
        
        Stack<Character> stack = new Stack<Character>();
        for(char c : arr) {
            if(c == '(') {
                stack.push(c);
            }
            else if(c == ')') {
                if(stack.isEmpty()) {
                    return false;
                }
                if(stack.peek() == '(') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            
            else if(c == '{') {
                stack.push(c);
            }
            else if(c == '}') {
                if(stack.isEmpty()) {
                    return false;
                }
                if(stack.peek() == '{') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            
            else if(c == '[') {
                stack.push(c);
            }
            else if(c == ']') {
                if(stack.isEmpty()) {
                    return false;
                }
                if(stack.peek() == '[') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        
        return stack.isEmpty();
    }
}

LeetCode题目：22. Generate Parentheses 产生所有的括号组合
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

class Solution {
    public List<String> result = new ArrayList<String>();
    public StringBuilder sb = new StringBuilder();
    
    public int leftParenthesisCount = 0;
    public int rightParenthesisCount = 0;
    
    public List<String> generateParenthesis(int n) {
        travel(n);
        
        return result;
    }
    
    public void travel(int n) {
        if(leftParenthesisCount <= n) {
            char[] validParenthesis = new char[]{};
            
            if(leftParenthesisCount == rightParenthesisCount) {
                validParenthesis = new char[] {'('};
            }
            if(leftParenthesisCount > rightParenthesisCount) {
                if(leftParenthesisCount < n) {
                    validParenthesis = new char[] {'(', ')'};
                }
                else {
                    validParenthesis = new char[] {')'};
                }
            }
            
            for(char c : validParenthesis) {
                sb.append(c);

                if(c == '(') leftParenthesisCount++;
                if(c == ')') rightParenthesisCount++;

                if(sb.length() == n * 2) {
                    result.add(sb.toString());
                } else {
                    travel(n);
                }

                // backtracking
                char t = sb.charAt(sb.length() - 1);
                sb.delete(sb.length() - 1, sb.length());

                if(t == '(') leftParenthesisCount--;
                if(t == ')') rightParenthesisCount--;
            }
        }
    }
}

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    
    // open为左括号的数目，close为右括号的数目
    public void backtrack(List<String> list, String str, int open, int close, int max){
        
        if(str.length() == max*2){
            list.add(str);
            return;
        }
        
        if(open < max)
            backtrack(list, str+"(", open+1, close, max);
        if(close < open)
            backtrack(list, str+")", open, close+1, max);
    }

LeetCode题目：32. Longest Valid Parentheses 最长的合法括号字符串
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

class Solution {
    public int longestValidParentheses(String s) {
        
        if(s == null) return 0;
        
        int maxLength = 0;
        int left = -1;
        
        // 记录每个元素的idx，stack 中缺省的 idx 即为已经匹配了的
        // 遍历 stack 中的所有gap，计算 maxLength
        Stack<Integer> st = new Stack<Integer>();
        
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                st.push(i);
            }
            else {
                if(!st.isEmpty()) {
                    st.pop();
                    
                    if(st.isEmpty()) {
                        maxLength = Math.max(maxLength, i - left);
                    }
                    else {
                        maxLength = Math.max(maxLength, i - st.peek());
                    }
                } else {
                    left = i;
                }
                
            }
        }
        
        return maxLength;
    }
}