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.
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') // Opening parenthesis; always put in the stack
stack.push(c);
else { // Closing parenthesis
if (stack.isEmpty()) // No more opening parenthesis to match the closing one
return false;
char top = stack.peek();
if ((top == '(' && c != ')') || (top == '[' && c != ']') || (top == '{' && c != '}'))
// The parenthesis at the top of the stack does not match the closing one
return false;
stack.pop(); // A match occurs; get the opening parenthesis out of the stack
}
}
if (stack.isEmpty()) // no opening parenthesis left unmatched
return true;
else
return false;
}
Read full article from LeetCode - Valid Parentheses | Darren's Blog
No comments:
Post a Comment