Parentheses总结

这篇文章总结leetcode中有关括号的问题，最简单的是判断输入的括号是否有效，例如“))”就不属于有效的括号，括号的题目无非是添加，删除，找到最长有效括号等。最长有效括号是一道DP问题，我们在DP总结中结合最长回文子串一起列出。下面列举几个基本的题目。

1，Valid Parentheses
给定一个字符串序列，它包含'(', ')', '{', '}', '[' , ']'，判断字符串是否是有效括号组成的。
例如："()" 和 "()[]{}" 是有效字符串；而 "(]" 和 "([)]" 就不是合法字符串。

我们用堆栈解决这道题，从第一个字符开始遍历，遇到‘(’ , '{' 或‘{’时，我们就把它压入到堆栈中，如果遇到‘)' , ']' 和‘}’时我们将字符出栈，并且与当前字符比较，如果匹配就继续查找，如果不匹配返回false。在遍历完之后，我们要检查堆栈是否为空，如果不为空，也返回false。
例如“((())”就会导致遍历结束后，栈中还有一个字符‘(’，而它是无效的字符串。代码如下：

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

2，Generate Parentheses
给定n对括号，列出所有可能的有效组合。
例如：n = 3
输出 ："((()))", "(()())", "(())()", "()(())", "()()()"

看到组合问题我们就想到用回溯法，回溯的条件是字符串的长度为2n时，我们就把它记录下来，然后回溯找其它的答案。当查找的时候，我们设定两个变量left和right，分别代表左括号的数量和右括号的数量，当左括号不为零时，我们可以继续添加左括号；而对于右括号，我们要保证再往下查找的时，右括号的数量大于左括号的数量（right > left）, 否则就会生成错误结果。
代码如下：

public class Solution {
    public List<String> generateParenthesis(int n) {
        LinkedList<String> list = new LinkedList<String>();
        int left = n;
        int right = n;
        String result = "";
        generateParent(n, left, right, result, list);
        return list;
    }
    
    public void generateParent(int n, int left, int right, String result, LinkedList<String> list) {
        if(result.length() == 2 * n) {
            list.add(result);
        }
        if(left > 0) generateParent(n, left - 1, right, result + "(", list);
        if(right > left) generateParent(n, left, right - 1, result + ")", list);
    }
}

3，Different Ways to Add Parentheses
给定一个字符串，字符串由数字和操作符组成，通过添加不同的括号列出所有可能的计算结果。
例如：输入："2*3-4*5"
输出：[-34, -14, -10, -10, 10]
结果是由以下的方式计算出来的：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

这道题我们用递归来解决，遍历字符串，当遇到操作符号时，我们就分别递归当前操作符的左边部分和右边部分，最终得到结果。代码如下：

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> list = new LinkedList<Integer>();
        if(!input.contains("+") && !input.contains("-") && !input.contains("*")) {
            list.add(Integer.valueOf(input));
            return list;
        }
        for(int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if(c == '+' || c == '*' || c == '-') {
                List<Integer> leftlist = diffWaysToCompute(input.substring(0, i));
                List<Integer> rightlist = diffWaysToCompute(input.substring(i + 1, input.length()));
                for(int leftvalue : leftlist)
                    for(int rightvalue : rightlist) {
                        switch (c) {
                            case '+':
                                list.add(leftvalue + rightvalue);
                                break;
                            case '-':
                                list.add(leftvalue - rightvalue);
                                break;
                            case '*':
                                list.add(leftvalue * rightvalue);
                                break;
                        }
                    }
            }
        }
        return list;
    }
}