Valid Parentheses

LeetCode笔记 阅读(509)

编号 : 20      
难度 : <font color="green">Easy</font>

# 题目 :  
>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  
>

# 解 :  
```Cpp
class Solution {
public:
    bool isValid(string s) {
        /* 查找匹配的括号 */
        map<char, char> match = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        
        /* 区分是左括号还是又括号 */
        string left = "([{";
        string right = ")]}";
        
        /* 用栈保存尚未闭合的左括号 */
        stack<char> openBrackets;
        
        for(auto& ch : s)
        {
            /* 左括号入栈 */
            if(left.find_first_of(ch) != string::npos)
            {
                openBrackets.push(ch);
            }
            else if(right.find_first_of(ch) != string::npos)
            {
                /* 没有左括号时读到右括号 */
                if(openBrackets.empty())
                {
                    return false;
                }
                
                char leftBracket = openBrackets.top();
                if(leftBracket == match[ch])
                {
                    /* 右括号匹配最后一个未闭合的左括号,左括号出栈 */
                    openBrackets.pop();
                }
                else
                {
                    /* 不匹配 */
                    return false;
                }
            }
        }
        
        /* 没有剩下未闭合的左括号 */
        return openBrackets.empty();
    }
};
```

# 分析 :  
这道题要求检查一组完全由括号组成的字符串,是否符合逻辑。   

用一个栈缓存未闭合的左括号,读到左括号就入栈,读到右括号就判断是否和栈顶的左括号匹配,如果匹配就出栈,不匹配就返回`false`。

读完整个字符串后,如果栈是空的,说明括号字符串符合逻辑,否则不符合逻辑。

Markdown使用 帮助


Cialis Achat En France  vorgoovats <a href=https://bansocialism.com/>cialis online cheap</a> secycoah Acquisto Levitra In Italia 

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

我有一头小毛驴,我从来也不骑。

匿名

好!顶!赞!

匿名

今天的风儿甚为喧嚣呢。

匿名

好!顶!赞!

匿名

今天的风儿甚为喧嚣呢。

匿名

今天的风儿甚为喧嚣呢。

匿名

好!顶!赞!

匿名

在山的那边,海的那边,有一群蓝精灵。