LeetCode - 20. 有效的括号
题目
20. 有效的括号 - 力扣（LeetCode）
思路
看到这道题，我首先分析了有效括号的特点。题目说左括号必须用相同类型的右括号闭合，必须以正确的顺序闭合，每个右括号都有一个对应的左括号。
这就想到了一个关键特性 - 括号的嵌套结构符合'后进先出'的特点。比如字符串'({[]})'，最内层的'[]'是最后开始的左括号，但却是最先需要匹配的。这种'后进先出'的特性，自然让我联想到了栈这种数据结构。
栈的特点就是后进先出(LIFO)，非常适合处理这种嵌套的匹配问题。我可以用栈来记录所有出现的左括号，然后当遇到右括号时，我需要的是最近遇到的左括号是否与之匹配，这正好对应栈顶元素。
解题步骤
- 创建一个空栈，用来存储遇到的左括号
- 创建一个哈希表，用来存储右括号和对应左括号的映射关系，比如 ')' 对应 '('
- 遍历字符串中的每个字符：
- 如果是左括号，直接入栈
- 如果是右括号，检查栈是否为空或栈顶元素是否与当前右括号匹配
- 如果栈为空或不匹配，返回false
- 如果匹配，弹出栈顶元素，继续遍历
- 遍历结束后，检查栈是否为空，为空则说明所有括号都匹配了，返回true；否则返回false
比如示例3中的 '[]'，我们遍历到 '[' 时将其入栈，然后遇到 ']'，检查栈顶是 '['，匹配成功，弹出栈顶，最后栈为空，所以返回true。
而示例3中的 '(]'，遍历到 '(' 时将其入栈，然后遇到 ']'，检查栈顶是 '('，与 ']' 不匹配，所以返回false。
这个算法的时间复杂度是O(n)，n是字符串长度，因为我们只需要遍历一次字符串。空间复杂度也是O(n)，最坏情况下可能需要将所有字符入栈。
我还注意到一些边界情况：如果字符串长度为奇数，肯定不是有效的括号字符串，因为括号必须成对出现；如果字符串为空，按定义应该返回true。
读者可能出现的错误写法
class Solution {
public:bool isValid(string s) {if(!s.size() || !s.size()%2 || s.size() == 1){return false;}stack<char> str;unordered_map<char,char> hash;hash['('] = ')';hash['['] = ']';hash['{'] = '}';for(int i = 0;i<s.size();i++){if(hash.count(s[i])){str.push(s[i]);}else if(s[i] == ')'){int ret = str.front();str.pop();if(ret == '('){continue;}else{return false;}}else if(s[i] == ']'){int ret = str.front();str.pop();if(ret == '['){continue;}else{return false;}}else if(s[i] == '}'){int ret = str.front();str.pop();if(ret == '{'){continue;}else{return false;}}}return true;}
};首先，判断条件有问题：
if(!s.size() || !s.size()%2 || s.size() == 1)
{return false;
}这里的逻辑不对。如果字符串为空，应该直接返回true（空字符串被视为有效）。另外，!s.size()%2的写法有问题，应该是s.size()%2 != 0来判断字符串长度是否为奇数。
其次，在处理右括号时，使用了str.front()而不是str.top()。在栈中，我们应该访问栈顶元素，而front()是用于队列的。而且栈中存放的是char类型的，这里你用int去接收也是错误的
还有一个问题是，代码中没有检查在弹出栈顶元素前栈是否为空，如果遇到右括号时栈为空，会导致程序崩溃。
最后，函数结束时没有检查栈是否为空。如果字符串中只有左括号没有右括号，栈不会为空，但函数会错误地返回true。
正确写法
class Solution {
public:bool isValid(string s) {if(s.size()%2 !=0){return false;}stack<char> str;unordered_map<char,char> hash;hash['('] = ')';hash['['] = ']';hash['{'] = '}';for(int i = 0;i<s.size();i++){if(hash.count(s[i])){str.push(s[i]);}else if(s[i] == ')'){if(str.size()){char ret = str.top();str.pop();if(ret == '('){continue;}else{return false;}}else{return false;}}else if(s[i] == ']'){if(str.size()){char ret = str.top();str.pop();if(ret == '['){continue;}else{return false;}}else{return false;}}else if(s[i] == '}'){if(str.size()){char ret = str.top();str.pop();if(ret == '{'){continue;}else{return false;}}else{return false;}}}if(str.size()){return false;}else{return true;}}
};代码结构上有重复逻辑。对于三种右括号的处理几乎完全相同，这导致代码冗长且不易维护。
class Solution {
public:bool isValid(string s) {if(s.size()%2 !=0){return false;}stack<char> str;unordered_map<char,char> hash;hash['('] = ')';hash['['] = ']';hash['{'] = '}';for(int i = 0;i<s.size();i++){if(hash.count(s[i])) //左括号{str.push(s[i]);}else{if(str.empty()){return false;}char top = str.top();str.pop();if(s[i] != hash[top]){return false;}}}return str.empty();}
};