【字符串/栈】有效的括号（leetcode20）

一、题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

二、分析

有效的括号应该满足：每一个左括号，在恰当的位置都会有一个右括号与之对应。

简单来讲，本题可看作是一个消消乐游戏，从左向右遍历字符串，当左括号找到恰当位置的右括号时，就将这对括号消掉。当遍历结束时，所有的括号对都消除了，那么字符串s满足要求，返回true；否则，返回false。

由于是按照从左向右固定的顺序遍历，所以先出现的左括号一定是后消掉的。因此，自然联想到使用栈的性质——先进后出，来解决此题。

对于本题，具体步骤如下：

• 从左向右依次遍历字符串的每一个字符
• 如果字符是左括号，则存入栈中；如果是右括号，则做进一步判断
• 如果是右括号，先判断此时栈是否为空。如果是空的，则右括号无法小消除，返回false；如果栈不是空的，再将此字符于栈顶元素进行比较，判断是否符合条件。
• 当遍历完所有字符元素，判断栈是否为空。如果是空，说明所有括号都消掉了，返回true；否则，返回fasle。

三、题解

根据以上的分析，C++实现如下：

class Solution {
public: stack<char> stk; unordered_map<char, char> pairs = { {'(', ')'}, {'[', ']'}, {'{', '}'} }; bool isValid(string s) { for(int i=0; i<s.size(); ++i) { if(s[i]=='(' || s[i]=='{' || s[i]=='['){ stk.push(s[i]); //如果是左括号，则存入栈中 } else{  //如果是右括号，则和栈顶元素进行比较 if(!stk.empty() && s[i]==pairs[stk.top()]){ stk.pop(); } else{ return false; } } } if(stk.empty()) return true; else return false; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

提交结果如下：

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/118579348