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.
一刷
题解：
一道基本的使用stack的题目。 Time Complexity - O(n)， Space Complexity - O(n)
test case:
"){"
"([])"
"(("
public class Solution {
public boolean isValid(String s) {
if(s == null || s.length() == 0) return true;
Stack<Character> stack = new Stack<Character>();
for(int i=0; i<s.length(); i++){
Character left = s.charAt(i);
if(left == '(' || left == '[' || left == '{' )
stack.push(left);
else{
if(stack.isEmpty()) return false;
char cur = stack.pop();
if(left == ']' && cur!='[') return false;
else if(left == '}' && cur!='{') return false;
else if(left == ')' && cur!='(') return false;
}
}
if(!stack.isEmpty()) return false;
return true;
}
}
二刷
class Solution {
public boolean isValid(String s) {
if((s.length()&1)!=0) return false;
Stack<Character> stack = new Stack();
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
if(ch == '[' || ch == '{' || ch == '(') stack.push(ch);
else{
if(stack.isEmpty()) return false;
char pop = stack.pop();
if((pop == '[' && ch == ']')
|| (pop == '(' && ch == ')')
|| (pop == '{' && ch == '}') ) continue;
else return false;
}
}
return stack.isEmpty();
}
}
follow up: 如果不是括号，而是<html>这种标记符号呢？
可以依然用上述的方法，然后在stack push('h')
