错误:AddressSanitizer:负大小参数:(size=-1)

Question

很抱歉这段混乱的代码，但我有一个问题。

我试图解决LeetCode的844任务。考虑到

给定两个字符串S和T，如果它们在空文本编辑器中键入时相等，则返回。#表示退格字符。

第一个示例

输入：S="ab#c"，T="ad#c">
输出：true
解释：S和T都变为"ac"。

第二个示例

输入：S="ab##"，T="c#d#">
输出：true
解释：S和T都变为"。

我在这里的解决方案：

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==错误：AddressSanitizer：负大小参数：(size=-1(
#8 0x7f585c70d82f(/lib/x86_64-linux-gnu/libc.so.6+0x2082f(/lib/x86_64-linux-gnu/libc.so.6+0x2082f(
===中止

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

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 += 2是在常规++i的基础上完成的

您的代码可以使用进行简化

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;
}

演示

然后，您的"字符串比较"：

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的大小不同，则在循环中有越界访问，或者忽略剩余的比较(但应该为false(
• 循环中的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);
}