LeetCode有效括号问题：数组替代栈的代码错误排查及疑问

问题描述 #

给定仅包含(、)、{、}、[ 和 ]的字符串s，判断输入字符串是否有效。有效字符串需满足：

• 开括号必须由相同类型的闭括号闭合；
• 开括号必须按正确顺序闭合；
• 每个闭括号都有对应的同类型开括号。

我的疑问与代码 #

多数人使用栈配合少量条件判断解决该问题，但我尝试用数组形式的字符串结合多个特定条件实现。想请教：我的代码存在什么问题？为何大家使用栈？栈解法的时间复杂度更优吗？

class Solution {
private:
    int i;
public:
    bool isValid(string s) {
        for(i=0;i<size(s);i+2){
            if(s[i]=='(' && s[i+1]!=')'){
                return false;
            }else if(s[i]=='{' && s[i+1]!='}'){
                return false;
            }else if(s[i]=='[' && s[i+1]!=']'){
                return false;
            }else{
                return true;
            }               
        }
    }
};

报错信息 #

第6行第28个字符：警告：表达式结果未使用 [-Wunused-value]
for(i=0;i<size(s);i+2){
_^

第17行第5个字符：错误：非void函数未在所有控制路径中返回值 [-Werror,-Wreturn-type]
}
^

生成1个警告和1个错误。

问题解答 #

你的代码存在的问题 #

• 循环更新语句错误：i+2只是计算了i加2的结果，但没有将值赋值给i，这会导致循环永远无法推进，陷入死循环，这就是警告的来源。正确写法应该是i += 2。
• 核心逻辑完全错误：你的代码默认所有有效括号都是相邻成对出现的，但实际有效括号支持嵌套，比如([])这种合法字符串，你的代码会检查s[0]是(，s[1]是[，直接返回false，完全不符合需求。另外，当字符串长度为奇数时，你的逻辑根本无法处理。
• 提前返回逻辑错误：第一次循环中只要当前成对括号匹配，就直接返回true，但后续可能存在不匹配的括号。比如()[(])，你的代码会在检查前两个()匹配后直接返回true，忽略后面的错误部分。
• 缺少返回路径：当字符串长度为0时，循环不会执行，函数没有返回任何值，这就是报错提示“非void函数未在所有控制路径中返回值”的原因。

为什么大家都用栈 #

栈的后进先出特性完美契合括号的嵌套规则——最后打开的括号必须最先闭合。具体逻辑是：

• 遇到开括号((/{/[)就压入栈；
• 遇到闭括号就检查栈顶元素是否是对应的开括号：如果匹配就弹出栈顶，不匹配则直接判定字符串无效；
• 遍历结束后，若栈为空则说明所有括号都正确闭合，否则存在未匹配的开括号。

这种逻辑能处理所有合法/非法场景，包括嵌套、顺序错误、不匹配等情况，逻辑清晰且覆盖全面。

栈解法的时间复杂度 #

栈解法的时间复杂度是O(n)，其中n是字符串长度。因为每个字符只会被压入栈一次、弹出栈一次，所有操作都是O(1)级别的。

而你的思路本身无法处理嵌套场景，硬要修改的话，比如反复扫描字符串删除成对括号，时间复杂度会达到O(n²)，远不如栈解法高效。

内容的提问来源于stack exchange，提问作者rachelle reena hn