[LeetCode] 20. Valid Parentheses 合法括号

2021年09月15日 阅读数：2

Given a string containing just the characters `'('``')'``'{'``'}'``'['` and `']'`, determine if the input string is valid.html

An input string is valid if:java

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.python

Example 1:app

```Input: "()"
Output: true
```

Example 2:ide

```Input: "()[]{}"
Output: true
```

Example 3:post

```Input: "(]"
Output: false
```

Example 4:url

```Input: "([)]"
Output: false
```

Example 5:code

```Input: "{[]}"
Output: true```

Java: Time: O(n), Space: O(n)

```public static boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<Character, Character>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (map.keySet().contains(curr)) {
stack.push(curr);
} else if (map.values().contains(curr)) {
if (!stack.empty() && map.get(stack.peek()) == curr) {
stack.pop();
} else {
return false;
}
}
}
return stack.empty();
}```

Java:

```public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}　　```

Python:

```class Solution:
# @return a boolean
def isValid(self, s):
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []　　```

Python: Time: O(n), Space: O(n)

```class Solution:
def isValid(self, s):
stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
for parenthese in s:
if parenthese in lookup:  # Cannot use if lookup[parenthese]: KeyError
stack.append(parenthese)
elif len(stack) == 0 or lookup[stack.pop()] != parenthese: # Cannot use not stack
return False
return len(stack) == 0```

Python: wo

```class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
m = {'(': ')', '[': ']', '{': '}'}
n = [')', ']', '}']
for i in s:
if i in m:
stack.append(i)
elif i in n and stack:
if m[stack.pop()] != i:
return False
else:
return False
return len(stack) == 0```

C++:

```class Solution {
public:
bool isValid(string s) {
stack<char> parentheses;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);
else {
if (parentheses.empty()) return false;
if (s[i] == ')' && parentheses.top() != '(') return false;
if (s[i] == ']' && parentheses.top() != '[') return false;
if (s[i] == '}' && parentheses.top() != '{') return false;
parentheses.pop();
}
}
return parentheses.empty();
}
};
```

[LeetCode] 22. Generate Parentheses

[LeetCode] 32. Longest Valid Parentheses

[LeetCode] 241. Different Ways to Add Parentheses

[LeetCode] 301. Remove Invalid Parentheses