Parentheses

Amazon面试题：判断有多少对括号，有落单的就return-1，否则return多少对，基本用个stack就搞定
EX: (())()()， return 4
(()())( ，retrurn -1
评：与leetcode的题不一样，但test case可以用32的测试，下面是自己写的，亲测可用。另外附加20，22题相似题，感觉需要会，20题相似，22题backtracking。

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length(); i++) {
            if(s.charAt(i) == '(') stack.push(c);
            else if(!stack.isEmpty()) {
                stack.pop();
            }
            else return -1;
        }
        return stack.isEmpty()?s.length()/2:-1;

    }
}

20. Valid Parentheses

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

22. Generate Parentheses

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        dfs(res,n,n,"");
        return res;
    }
    public void dfs(List<String> res,int l,int r,String s){
        if(l>r||l<0||r<0) return;
        if(l==0&&r==0){
            res.add(s);
            return;
        }
        if(l>0) dfs(res,l-1,r,s+"(");
        if(r>0) dfs(res,l,r-1,s+")");
    }
}