代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        stack <char> t;
        for(char n : s)
        {
            if (n == '(')                t.push(')');
            else if (n == '{')           t.push('}');
            else if (n == '[')           t.push(']');
            else 
            {
                if(t.empty() || t.top() != n)      return false; //此时n为三种右括号之一，而栈顶也是三种右括号之一
                else        t.pop(); 
            }        
        }
        return t.empty();
    }
};

使用map的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> mp = { { '}','{' }, { ')','(' }, { ']','[' } };
        stack <char> t;
        for(char n : s)
        {
            if(n == '(' || n == '[' || n == '{')    t.push(n);
            else
            {
                if(t.empty() || t.top() != mp[n])  return false;
                else        t.pop();
            }
        }
        return t.empty();
    }
};

不使用栈（效率很低）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> mp = { { '{','}' }, { '(',')' }, { '[',']' } };
        int i = 0;
        while(i < s.size())
        {
            if(mp[s[i]] == s[i+1] && s[i+1] !='\0')
            {
                s.erase(i,2);
                i = -1;
            }
            i++;
        }
        return !s.size();
    }
};