20. Valid Parentheses / Valid Parentheses

leet和lint有轻微的不同，lint还要写个function考虑一下输入字符是否合法。

和LC150很像，if，else-if，else的逻辑结构。

public class Solution { 
    public boolean isValid(String s) {
        char[] res = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < res.length; ++i) {
            if (res[i] == '(') { 
                stack.push(')');
            } else if (res[i] == '[') { 
                stack.push(']');
            } else if (res[i] == '{') { 
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != res[i]) return false;
        }
        return stack.isEmpty();
    }
}

22. Generate Parentheses

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) return result;

        dfs(result, new StringBuilder(), n, n);
        return result;
    }
    private void dfs(List<String> result, StringBuilder sb, int left, int right) {
        if (left == 0 && right == 0) result.add(sb.toString());

        int length = sb.length();

        if (left > 0) {
            sb.append('(');
            dfs(result, sb, left - 1, right);
            sb.setLength(length);
        }
        if (right > left) {
            sb.append(')');
            dfs(result, sb, left, right - 1);
            sb.setLength(length);
        }
    }
}

301. Remove Invalid Parentheses

这道题论坛第一的解法和分析简直拍案叫绝。

We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter. The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix.

To make the prefix valid, we need to remove a ‘)’. The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.

After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ‘)’ in two steps only with a different order. For this, we keep tracking the last removal position and only remove ‘)’ after that.

Now one may ask. What about ‘(‘? What if s = ‘(()(()’ in which we need remove ‘(‘? The answer is: do the same from right to left. However a cleverer idea is: reverse the string and reuse the code!

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        remove(s, result, 0, 0, new char[]{'(', ')'});
        return result;
    }
    private void remove(String s, List<String> result, int starti, int startj, char[] par) {
        for (int count = 0, i = starti; i < s.length(); ++i) {
            if (s.charAt(i) == par[0]) count++;
            if (s.charAt(i) == par[1]) count--;
            if (count >= 0) continue;

            for (int j = startj; j <= i; ++j) {
                if (s.charAt(j) == par[1] && (j == startj || s.charAt(j - 1) != par[1])) {
                    remove(s.substring(0, j) + s.substring(j + 1, s.length()) + "", result, i, j, par);
                }
            }
            return;
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if (par[0] == '(') {
            remove(reversed, result, 0, 0, new char[]{')', '('});
        } else {
            result.add(reversed);
        }
    }
}