LeetCode 20 — Valid Parentheses

题目描述

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:
Input: "()"
Output: true

Example 2:
Input: "()[]{}"
Output: true

Example 3:
Input: "(]"
Output: false

Example 4:
Input: "([)]"
Output: false

Example 5:
Input: "{[]}"
Output: true

这道题的主要要求就是括号的匹配，那么我们很自然的想到我们可以借助栈来解决这道问题，对于这道题的解释也很简单，首先就是基本的括号匹配，如果是字符串为空的话，也判断为匹配成功，因此，我们可以写出一下代码：

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

    bool isMatch(char s, char p)
    {
        if((s == '(' && p == ')')|| (s == '{' && p == '}')|| (s == '[' && p == ']'))
            return true;
        else
            return false;
    }
};

这就是一种常规的解法，使用栈，并且将匹配成功的出栈，最后检查栈里面是否还有剩余，就是一个很好的解决办法，之后在网上看别人的答案的是偶，发现了另外一种想法，感觉也挺不错的，所有就po出来：

bool isValid(string s) 
{
    if(s.length() == 0){
        return true;
    }
    stack<char> st;
    st.push(s[0]);
    for(int i = 1; i < (int)s.length(); i++)
    {
        char c = s[i];
        char ret = getPaif(c);
        if(ret == 0)
        {
            st.push(c);
        }else{
            if(st.empty() || st.top() != ret){
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}

char getPair(char c) {
    char ret = 0;
    switch (c) {
       case ')':
            ret = '(';
            break;
        case '}':
            ret = '{';
            break;
        case ']':
            ret = '[';
            break;
        default:
            break;
    }
    return ret;
}

这种方法不是直接匹配，而是通过一个函数，找到我想要的那个符号，如果接下的符号和我想要的不是一个的话，我就直接返回false，也是一个不错的想法。