Created
April 2, 2014 22:12
-
-
Save Jeffwan/9944308 to your computer and use it in GitHub Desktop.
Valid Parentheses @leetcode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode; | |
import java.util.Stack; | |
/** | |
* Solution: Stack left --> push, right -->pop and compare | |
* Didn't check if s is valid. like "", a little vague here, need to ask interviewer. | |
* | |
* The problem says this string contains just these 6 char but not other! read carefully! | |
* the last part check is stack.size() > 0. use return stack.isEmpty() to refactor. | |
* | |
* @author jeffwan | |
* @date Apr 2, 2014 | |
*/ | |
public class ValidParentheses { | |
public boolean isValid(String s) { | |
Stack<Character> stack = new Stack<Character>(); | |
for (Character c : s.toCharArray()) { | |
if ("{([".contains(String.valueOf(c))) { | |
stack.push(c); | |
} else { | |
if (!stack.isEmpty() && isValidHelper(stack.peek(), c)){ | |
stack.pop(); | |
} else { | |
return false; | |
} | |
} | |
} | |
return stack.isEmpty(); | |
} | |
private boolean isValidHelper(char c1, char c2) { | |
return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') | |
|| (c1 == '[' && c2 == ']'); | |
} | |
// My solution -- thought is clear but code is not very clear. | |
public static boolean isValid2(String s) { | |
Stack<Character> stack = new Stack<Character>(); | |
for (int i = 0; i < s.length(); i++) { | |
char c = s.charAt(i); | |
if (c == '(' || c == '{' || c == '[') { | |
stack.push(c); | |
continue; | |
} | |
// handle situation ) } ] appears but stack is null. stack.pop() will throw exception. | |
if ((c== ')' || c== '}' || c== ']') && stack.size() == 0) { | |
return false; | |
} | |
if (c == ')') { | |
if ('(' != stack.pop()) { | |
return false; | |
} | |
} | |
if (c == '}') { | |
if ('{' != stack.pop()) { | |
return false; | |
} | |
} | |
if (c == ']') { | |
if ('[' != stack.pop()) { | |
return false; | |
} | |
} | |
} | |
if (stack.size() != 0) { | |
return false; | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment