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;
}
}
- 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();
}
}
- 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+")");
}
}
