题目

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

思路

leetcode上的解答是这样的：

先考虑简单的情况：只有一种括号

![](https://i.loli.net/2019/05/21/5ce3d69f2d3d896804.jpg)
图1：只有一种括号
定义一个计数器left，如果我们遇到一个开括号，则计数器left加1；如果遇到一个闭括号，此时有两种情况，一是当前left=0，这说明没有配对的开括号，表达式无效；二是left>0，说明还有没配对的开括号，left--。
但是实际情况不止一种括号，但是我们发现，为了保证表达式的每一个子表达式都是也是有效的，每一个闭括号总是与左起最近的开括号是匹配的，如图2。
![](https://i.loli.net/2019/05/21/5ce3d848c7b0852829.jpg)
图2：多个括号的情况
这个时候就要用到栈。在表示问题的递归结构时，由于我们不清楚整体的结构，无法从里到外的解决问题，此时栈可以帮助我们递归地解决问题，从外到内地解决问题。
于是本题的解题思路如下：
* 1.初始化一个堆栈，并初始化一个映射表（用来处理不同种类的括号）；
* 2.循环处理所有括号
* 如果是开括号，则push进栈即可；
* 如果是闭括号，那么就需要检查栈顶的元素，如果栈顶的开括号与当前的闭括号匹配（通过查找建立的映射表匹配），则pop出栈；如果不匹配，说明表达式无效；

3.当处理完所有括号后，如果栈中还有元素，说明表达式无效。

就想在玩一个消消乐，只有当开括号和闭括号匹配的时候才能消掉这一对括号。

Tips

栈

一种线性存储表。它有以下两种特性：

栈中数据按照后进先出（last-in, first-out, LIFO）的方式进栈和出栈的。
只能从栈顶（top）操作数据。

我们可以把它想象成几个盘子堆在弹簧上的场景。

![](https://i.loli.net/2019/05/21/5ce3dc0e1aab537652.jpg)
图4：栈的结构示意图
**入栈（push）**
![](https://i.loli.net/2019/05/21/5ce3ddf61390738627.jpg)
图5：入栈示意图
**出栈（pop）**
![](https://i.loli.net/2019/05/21/5ce3de567d21652302.jpg)
图6：出栈示意图

C++

 bool isValid(string s) {

        map<char,char> table={ {')', '('}, {']', '['}, {'}', '{'} };

        if( s.size()== 0 )

            return true;

        stack<char> cStack;

        for(int i = 0;i<s.size(); i++){

            if(s[i] == '(' || s[i] == '[' || s[i] == '{')

                cStack.push(s[i]);

            else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){

                if(cStack.empty())

                    return false;

                char popChar = cStack.top();

                if(popChar == table[s[i]]){

                    cStack.pop();

                    continue;

                }

                else

                    return false;

            }

        }

        if(cStack.empty())

            return true;

        return false;

    }

巴特西

20. Valid Parentheses[E]有效的括号

题目

思路

Tips

栈

C++

Python

最新文章

热门文章