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
Time: O(N)
Method 1:
class Solution: def isValid(self, s: str) -> bool: if s is None: return False pair = {')': '(', '}': '{', ']':'['} res = [] for char in s: if char in pair.values(): res.append(char) elif char in pair.keys(): if res and res[-1] == pair.get(char): res.pop() else: return False else: return False return res == []
class Solution { public boolean isValid(String s) { LinkedList<Character> stack = new LinkedList<>(); for (char c: s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.offerFirst(c); } else if (c == ']') { if (stack.isEmpty() || stack.pollFirst() != '[') { return false; } } else if (c == ')') { if (stack.isEmpty() || stack.pollFirst() != '(') { return false; } } else if (c == '}') { if (stack.isEmpty() || stack.pollFirst() != '{') { return false; } } } return stack.isEmpty(); } }
Method 2:
class Solution: def isValid(self, s: str) -> bool: if s is None: return False left = ['(', '{', '['] right = [')', '}', ']'] res = [] for char in s: if char in left: res.append(char) elif char in right: if len(res) != 0 and self.match(res[-1], char): res.pop() else: return False return len(res) == 0 def match(self, l, r): return l=='(' and r==')' or l=='{' and r=='}' or l=='[' and r==']'