20. Valid Parentheses

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.

这道题的意思是括号匹配，一开始还以为两个括号是挨着的，后来提交代码发现测试用例中有([])才发现自己too naive。

一开始的代码

bool isMatch(char a,char b)
{
    switch (a)
    {
        case '(':
            if (b==')') {return true;}
            else return false;
        case '{':
            if (b=='}') {return true;}
            else return false;
        case '[':
            if (b==']') {return true;}
            else return false;
        default:
            return false;
    }
}

bool isValid(string s)
{
    if (s.length()<2)
    {
        return false;
    }
    int i=0;int j=i+1;
    while (j<s.length())
    {
        if (!isMatch(s[i],s[j]))
        {
            return false;
        }
        i+=2;j+=2;		
    }
    if (j==s.length()+1)//注意这里的条件，因为在匹配结束后j会加2，所以当完全匹配时j的值是len+1而不是len-1
    {
        return true;
    }
    else return false;

}	

算法思路

利用栈的思想，对所有字符串压栈，然后取一个字符和栈顶元素匹配，如果可以匹配则pop，指针后移。如果不能匹配则压栈。最后看栈内是否为空。

代码

class Solution {
public:
bool isMatch(char a,char b)
{
    switch (a)
    {
        case '(':
            if (b==')') {return true;}
            else return false;
        case '{':
            if (b=='}') {return true;}
            else return false;
        case '[':
            if (b==']') {return true;}
            else return false;
        default:
            return false;
    }
}
bool isValid(string s)
{
    if (s.length()<2)
    {
        return false;
    }
    stack<char> st;
    st.push(s[0]);
    int i=1;
    while(i<s.length())	/////////////
    {
        if (!st.empty()) //////////////
        {
            if(isMatch(st.top(),s[i]))
                st.pop();
            else {st.push(s[i]);} 
            
        }
        else {st.push(s[i]);}
        i++;
    }
    if (st.empty())
    {
        return true;
    }
    else return false;

    }
};

时间：4ms

需要注意的问题：

1. 对于算法结束条件的判断，不能是while(!st.empty() && i<s.length)，因为在{})这种情况下，前面两个匹配完了，栈为空，此时跳出循环，后面的一个}没有进栈。
   采用的方法是先判断是否溢出，然后判断栈是否为空，如果空则当前字符进栈，否则判断是否匹配，如果匹配则弹出，不匹配则进栈。

2. 另外对于循环变量i的设置，要判断i是否超过s的长度，不能溢出。采用的方案是i=0的时候进栈，i指向的是当前字符串的第一个元素，判断条件是i<s.length()。

自己写的真是又臭又长，贴一个简洁的：

    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case '(': 
                case '{': 
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }