LintCode 423 · Valid Parentheses.java

	// Approach #1 - T O(n), S O(n), given that n is the length of the input string.
	// Error-prone: Character instead of Characters
	public class Solution {
	/**
	* @param s: A string
	* @return: whether the string is a valid parentheses
	*/
	public boolean isValidParentheses(String s) {
	// write your code here
	if (s == null || s.length() == 0) {
	return true;
	}
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i < s.length(); i++) {
	char letter = s.charAt(i);
	if (isOpening(letter)) {
	stack.push(letter);
	} else {
	if (stack.isEmpty()) {
	return false;
	} else if (isMatching(stack.peek(), letter)) {
	stack.pop();
	} else {
	return false;
	}
	}
	}
	if (!stack.isEmpty()) {
	return false;
	}
	return true;
	}
	private boolean isOpening(char ch) {
	return (ch == '(' || ch == '[' || ch == '{');
	}
	private boolean isMatching(char ch1, char ch2) {
	return (ch1 == '{' && ch2 == '}') || (ch1 == '(' && ch2 == ')') || (ch1 == '[' && ch2 == ']');
	}
	}

view raw LintCode 423 · Valid Parentheses.java hosted with ❤ by GitHub