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();
    }
}