当前位置 博文首页 > 公仔面:leetcode刷题/字符串 844.比较含退格的字符串(0ms)
给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
输入:S = "ab#c", T = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。
示例 2:
输入:S = "ab##", T = "c#d#"
输出:true
解释:S 和 T 都会变成 “”。
示例 3:
输入:S = "a##c", T = "#a#c"
输出:true
解释:S 和 T 都会变成 “c”。
示例 4:
输入:S = "a#c", T = "b"
输出:false
解释:S 会变成 “c”,但 T 仍然是 “b”。
两个字符串分开处理,遍历字符串然后找"#",如果找到"#"分两种情况:
- 如果是在首位就删除"#",然后下标回退一格;
- 如果不是在首位需要删除"#"和前面的字符,然后下标回退两位
删除完之后比较两个字符串即可
class Solution {
public:
bool backspaceCompare(string s, string t) {
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '#')
{
if (i == 0)
{
s.erase(i, 1);
i--;
}
else
{
s.erase(i - 1, 2);
i = i - 2;
}
}
}
for (int i = 0; i < t.size(); i++)
{
if (t[i] == '#')
{
if (i == 0)
{
t.erase(i, 1);
i--;
}
else
{
t.erase(i - 1, 2);
i = i - 2;
}
}
}
if (t == s)
return true;
return false;
}
};
cs这道题直接用暴力求解,复杂度为O(M + N),用双指针复杂度O(M + N).所以我直接运用暴力直接求.