leetcode题解-20.有效的括号
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true 示例 2:
输入: "()[]{}" 输出: true 示例 3:
输入: "(]" 输出: false 示例 4:
输入: "([)]" 输出: false 示例 5:
输入: "{[]}" 输出: true
解决方法
这道题就非常适合用我们之前介绍过的栈（参考《如何自己实现一个栈》）这种数据结构来解决。怎么处理呢？我们发现括号都是成对的，如果成对的括号，并且括号中间的括号也可以成对，那么整个字符串就是有效的。比如说：
"{[]}"在{}之间的[]是成对的，它们可以互相抵消掉，之后{}也是成对的。我们可以利用栈，遍历整个字符串，遇到左括号，入栈，遇到右括号，检查栈中是否是左括号，如果是，那么就将左括号出栈，右括号也不入栈，相当于将成对的括号“消掉”了。如果字符串的是合法的，那么最终栈为空，否则栈不为空。
我们来看一个例子：
“{[]}”遇见左大括号，入栈：
栈顶 | ||||
|---|---|---|---|---|
{ |
遇见左方括号，入栈：
栈顶 | ||||
|---|---|---|---|---|
{ | [ |
遇见右方括号，检查栈顶是左方括号，出栈：
栈顶 | ||||
|---|---|---|---|---|
{ |
遇见右大括号，检查栈顶是左大括号，出栈：
此时扫描完毕，并且栈为空，因此该字符串合法。
我们再来看一个非法的例子：
”([)]“首先遇到左小括号，入栈：
栈顶 | ||||
|---|---|---|---|---|
( |
遇到左方括号,入栈：
栈顶 | ||||
|---|---|---|---|---|
( | [ |
遇到右小括号，检查栈顶是否有左小括号，发现没有，入栈(其实这个时候就可以判断字符串不合法了)：
栈顶 | ||||
|---|---|---|---|---|
( | [ | ) |
遇到右中括号，检查栈顶是否有左方括号，发现没有，入栈：
栈顶 | ||||
|---|---|---|---|---|
( | [ | ) | ] |
扫描完成后，发现栈不为空，因此字符串不合法。
代码实现
在实现代码的时候，需要注意以下几点：
- 遇见第一个右括号无匹配时即退出
- 由于输入字符串长度可能较大，因此不适合使用静态数组
- 判断是否有左括号前检查栈是否为空
bool isValid(char* s) {
if(NULL == s)
return false;
int len = strlen(s);
/*使用数组作为栈，申请内存*/
char *stack = (char*)malloc(len * sizeof(char));
if(NULL == stack)
return false;
int topOfStack = -1;
while(0 != *s)
{
/*遇见左括号入栈*/
if('{' == *s || '[' == *s || '(' == *s)
{
//printf("push %c to stack\n",*s);
topOfStack++;
stack[topOfStack] = *s;
}
/*如果此时栈为空，说明之前都没有左括号，因此肯定不匹配，直接退出*/
else if(topOfStack == -1)
{
topOfStack++;
break;
}
/*遇见右括号，栈顶是左括号，出栈*/
else if(('}' == *s && '{' == stack[topOfStack] )||
(')' == *s && '(' == stack[topOfStack]) ||
( ']' == *s && '[' == stack[topOfStack]))
{
topOfStack--;
}
/*右括号，并且栈顶不是左括号，肯定不匹配，直接退出*/
else if('}' == *s || ']' == *s || ')' == *s )
{
topOfStack++;
break;
}
s++;
}
free(stack);
/*判断栈是否为空*/
return topOfStack == -1;
}总结 本文利用栈结构在O(n)时间复杂度，O(n)空间复杂度解决了括号匹配问题。你还有什么解法？欢迎留言。