Problem
Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Solution
We can use a stack to help matching same type parentheses. When we saw an open brackets, we push that into stack. When we saw a close brackets, we pop an element from the stack. If the top element on the stack matches the type, we continue. If the stack is empty or the element type is not matching, we detected an invalid string.
import java.util.*;
class Solution {
public static void main(String[] args) {
String str = "([)]";
System.out.println(valid(str));
}
private static boolean valid(String str) {
Stack<Character> stack = new Stack<>();
for(char c : str.toCharArray()) {
if(c == '{' || c == '[' || c == '(') {
stack.push(c); //(
} else if(c =='}') {
if(stack.isEmpty())
return false;
char tmp = stack.pop();
if(tmp != '{')
return false;
} else if(c ==']') {
if(stack.isEmpty())
return false;
char tmp = stack.pop();
if(tmp != '[')
return false;
} else if(c ==')') {
if(stack.isEmpty())
return false;
char tmp = stack.pop();
if(tmp != '(')
return false;
} else {
throw new RuntimeException("illegal character");
}
}
if(!stack.isEmpty())
return false;
return true;
}
}
The time complexity is O(N) and the space complexity is O(N)
