ERROR: AddressSanitizer: negative-size-param: (size=-1)

Question

抱歉，代码乱七八糟，但我有一个问题。

我试图解决 LeetCode 的 844 任务。鉴于

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

第一个示例

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

第二个例子

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

我的解决方案：

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        vector<char> a;
        vector<char> b;
        int id = 0; 
        for(int i = 0; i < S.length(); i++){
            a.push_back(S[i]);
            id++;
            if(S[i]=='#'){
                a.erase(a.begin()+id-2);
                id--;
                a.erase(a.begin()+id-1);
                id--;
            }
            if(S[i+1]=='#'){
                a.erase(a.begin()+id-1);  
                id--;
                i+=2;
            } 
        }id = 0;
        for(int i = 0; i < T.length(); i++){  
            b.push_back(T[i]);
            id++;
            if(T[i]=='#'){
                b.erase(b.begin()+id-2);
                id--;
                b.erase(b.begin()+id-1);
                id--;
            }
            if(T[i+1]=='#'){
                b.erase(b.begin()+id-1);
                i+=2;
            }
        }
        bool x;
        if(a.size()==0) x = true;
        else{
            for(int i = 0; i < a.size(); i++){
                if(a[i]==b[i]) x = true;
                else x = false;
            }
        }return x;
    }
};
//Input: S = "ab##", T = "c#d#"

运行时错误消息

=================================================================
==32==ERROR: AddressSanitizer: negative-size-param: (size=-1)
#8 0x7f585c70d82f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x602000000151 is located 0 bytes to the right of 1-byte region [0x602000000150,0x602000000151)
allocated by thread T0 here:
#5 0x7f585c70d82f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
==32==ABORTING

但是它给了我这样的错误。我认为这里的一切都很好。我的错误在哪里？

Answer 1

您的代码中有几个问题

int id = 0; 

for (int i = 0; i < S.length(); i++){
    a.push_back(S[i]);
    id++;
    if (S[i]=='#'){
        a.erase(a.begin()+id-2);
        id--;
        a.erase(a.begin()+id-1);
        id--;
    }
    if(S[i+1]=='#'){
        a.erase(a.begin()+id-1);  
        id--;
        i+=2;
    } 
}

您没有将 '#' 作为第一个字符（或额外的 '#'）处理。

i == S.size() - 1

S[i+1]越界
除了常规 ++i 之外，您的 i += 2 已完成。

您的代码可以简化为：

std::string backspace_string_simplification(const std::string& s)
{
    std::string res;

    for (char c : s) {
        if (c != '#') {
            res.push_back(c);   
        } else if (!res.empty()) {
            res.pop_back();   
        }
    }
    return res;
}

Demo

那么，你的"string comparison":

bool x;
if (a.size() == 0)
    x = true;
else {
    for(int i = 0; i < a.size(); i++) {
        if(a[i]==b[i]) x = true;
        else x = false;
    }
}
return x;

当a为空时，如果b也为空，则字符串相等。
如果 a 和 b 的大小不同，您要么在循环中越界访问，要么忽略剩余的比较（而它应该是假的）。
循环中的 if 等同于 x = (a[i] == b[i])，因此您的循环等同于（正确大小）x = a.back() == b.back().

您可以简单地执行 return a == b;（std::string 和 std::vector<char> 处理）。

导致

bool backspaceCompare(string lhs, string rhs) {
    return backspace_string_simplification(lhs) == backspace_string_simplification(rhs);
}

ERROR: AddressSanitizer: negative-size-param: (size=-1)

ERROR: AddressSanitizer: negative-size-param: (size=-1)

c++

address-sanitizer