Given a string containing just the characters
'(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order,
Solution:
When met brackets questions, stack-based solution seems to be a good choice.
"()" and "()[]{}" are all valid but "(]" and "([)]" are not.Solution:
When met brackets questions, stack-based solution seems to be a good choice.
public class Solution {
public boolean isValid(String s) {
if(s.length() == 0 || s.length() % 2 != 0) return false;
Stack stack = new Stack();
for(int i = 0; i < s.length(); i++){
int cur = getIndex(s.charAt(i));
if(cur == getIndex('(') || cur == getIndex('[') || cur == getIndex('{')) {
stack.push(cur);
}
else{
if(stack.isEmpty()) return false;
int out = stack.pop();
if (cur - out != 1) return false; //doesn't match
}
}
if(stack.isEmpty()) return true;
else return false;
}
public int getIndex(char c){
char[] symbols = {'(',')','[',']','{','}'};
for(int i = 0; i < symbols.length; i++){
if(symbols[i] == c) return i;
}
return -1;
}
}
No comments:
Post a Comment