Leetcode提交失败：minRemoveToMakeValid函数处理后字符串反转末尾出现空格的问题排查

我实在搞不懂为什么执行字符串反转操作后，处理完的字符串末尾总是留着空格字符，这直接导致我的Leetcode提交结果出错了。下面是我写的解决方案代码，麻烦帮我排查下问题出在哪：

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string str = "";
        int n = s.length();
        int open=0;
        for(int i=0;i<n;i++){
            if(s[i]=='('){
                open++;
            }else if(s[i]==')'){
                open--;
                if(open<0){
                    open=0;
                    continue;
                }
            }
            str+=s[i];
        }
        open=0;
        string s2="";
        for(int i=n-1;i>=0;i--){
            if(str[i]==')'){
                open++;
            }else if(str[i]=='('){
                open--;
                if(open<0){
                    open=0;
                    continue;
                }
            }
            s2=s2+str[i];
        }
        reverse(s2.begin(),s2.end());
        return s2;
    }
};

问题排查与修复 #

咱们来揪出这个问题的根源——你在第二个反向遍历的循环里犯了一个容易忽略的小错误：

你第一个循环处理后得到的str，长度大概率比原字符串s短（因为你跳过了那些无效的右括号），但第二个循环却依然用原字符串的长度n来遍历，从i = n-1开始往回走。这就会导致你访问str[i]的时候，i可能超过了str的实际长度，属于数组越界访问！

越界访问的结果是不确定的，有时候会读到内存里的空格或者其他随机字符，这些字符被加到s2里，反转之后就出现在结果字符串的末尾了，这就是你提交失败的原因。

修复方法很简单，把第二个循环的遍历范围改成基于str的实际长度：

open=0;
string s2="";
int m = str.length(); // 改用处理后字符串str的长度
for(int i=m-1;i>=0;i--){ // 遍历str的最后一位到第一位
    if(str[i]==')'){
        open++;
    }else if(str[i]=='('){
        open--;
        if(open<0){
            open=0;
            continue;
        }
    }
    s2=s2+str[i];
}

这样修改后，你只会遍历str中实际存在的有效字符，不会再出现越界访问的情况，那些莫名其妙的空格也就不会出现在结果里了。

内容的提问来源于stack exchange，提问作者Terry Mathelon