Given a string containing just the characters '('
,')'
,'{'
,'}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.
Subscribe to see which companies asked this question
解题思路
借助栈来实现:
- 如果为左括号则入栈;
- 如果为右括号, 若:
- 栈顶为与之匹配的左括号,则出栈。
- 否则,返回false。
- 最后,返回
stack.empty()
。
实现代码
C++:
// Runtime: 0 ms
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> mymap = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
stack<char> mystack;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
{
mystack.push(s[i]);
}
else if (!mystack.empty() && (mymap[mystack.top()] == s[i]))
{
mystack.pop();
}
else
{
return false;
}
}
return mystack.empty();
}
};
Java:
// Runtime: 2 ms
public class Solution {
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<Character, Character>();
Stack<Character> stack = new Stack<Character>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
stack.push(s.charAt(i));
}
else if (!stack.empty() && map.get(stack.peek()).equals(s.charAt(i))) {
stack.pop();
}
else {
return false;
}
}
return stack.empty();
}
}
时间: 2024-11-27 04:17:53