[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:

  1. Open brackets must be closed by the same type of brackets.
  2. 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

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断给定的字符串是否为有效括号序列。

有效字符串需满足:

  1. 左侧括号必须与之配对的右侧括号进行配对。
  2. 左侧的括号配对的顺序必须要正确。

注意空字符串也被判定为有效的输入字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

本题主要是栈知识的考察,直接符合栈的规律,如果是左侧括号则直接入栈即可,如果碰到右侧括号则应该出栈,而且如果是合法的括号序列,此时出栈的括号一定是与之配对的括号,

否则,该序列就是非法的括号序列。

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

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]20.valid parentheses

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/210.html

相关文章