【Leetcode刷题随笔】844 比较含退格的字符串

1. 题目描述

给定 s 和 t 两个字符串，比较 s 和 t 是否在删除所有由 # 字符表示的退格操作后相等。退格操作会删除其前面（不包括 # 本身）的一个字符，如果前面没有字符则忽略该 #。如果字符串的末尾有多个退格符，它们会相互抵消，直到没有退格符剩余或者所有字符都被删除。

示例 1：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”，因为#前面的b和d都被删除。

示例 2：
输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”，两个#则表示删除其前面部分两个字符。

原题链接： [844]。

2. 解题方法

2.1 方法一：指针法

由于只有当字符后面跟了退格符才需要删除该字符，而不需要考虑前面是否跟了退格符，因此从前往后处理是不方便的，因为在遍历到字符的时候不好判断其后面的情况。故可以从后往前遍历，先遍历到退格符，就很方便判断下一个遍历的字符是否需要删除。

在实现时，可以定义双指针分别指向两个字符串的末尾，并定义一个跳过计数器skip来统计退格符的数量 （题目说是删除，但执行中是跳过，因为题目只要求返回true或fals而不要求返回删除完字符后的字符串，所以跳过需要退格的字符，比较剩余字符是否相等即可）。

• 当遍历到一个#时，我们让skip加一，同时不对#进行处理，直接跳过（通过将指针左移一位实现）。
• 当遍历到一个普通字符时，我们考虑两种情况：
  • 如果skip为1，说明上一步遍历到了#，并且将其跳过了，此时需要将现在遍历到的普通字符也跳过并把skip减1（通过指针和skip都减一实现）。
  • 如果skip为0，说明刚刚没有遍历到#，该字符不需要跳过，而是进入比较环节，和另一个字符串遍历到的不需要被跳过的普通字符比较是否相等。
• 当两个字符串都遍历到不需要被删除的普通字符，则对二者进行比较，若不相等则返回false。

2.2 方法二：利用栈思想重构字符串

方法一通过跳过的方式实现比较，实质上没有对原字符串做删改。

也可以通过对原字符串进行重构的方式来比较，利用出栈入栈的思想实现。具体地说：

• 如果遍历到普通字符，进栈。
• 如果遍历到退格符，不进栈，且将栈顶元素弹出。
• 遍历完毕之后比较栈内剩余元素是否相等。

这种方法比方法一更好理解。

3. 代码实现（C语言）

3.1 方法一实现

bool backspaceCompare(char* s, char* t){
    int i = strlen(s) - 1;
    int j = strlen(t) - 1;
    int skip_s = 0, skip_t = 0;
    while(i >= 0 || j >= 0){
        while(i >= 0){
            if(s[i] == '#'){
                skip_s++;
                i--;
            }
            else if(skip_s > 0){
                skip_s--;
                i--;
            }else{
                break;
            }
        }
        while(j >= 0){
            if(t[j] == '#'){
                skip_t++;
                j--;
            }
            else if(skip_t > 0){
                skip_t--;
                j--;
            }else{
                break;
            }
        }
        if(i >= 0 && j >=0){
            if(s[i] != t[j]){
                return false;
            }
        }else{
            if(i >= 0 || j >= 0){
                return false;
            }
        }
        i--;
        j--;
    }
    return true;
}

代码解释：

1. 初始化：
   • i 和 j 分别初始化为字符串 s 和 t 的最后一个字符的索引。
   • skip_s 和 skip_t 分别用于记录字符串 s 和 t 中需要跳过的字符数量（由退格符引起）。
2. 外层循环：
   • 使用while(i >= 0 || j >= 0)作为循环条件，确保只要有一个字符串还没有被完全处理（即索引不小于0），就继续循环。
3. 处理字符串 s 中的退格符：
   • 内层while循环（针对s）检查当前字符是否为退格符。
   • 如果是，则增加skip_s的值，并将索引 i 递减以跳过当前退格符检查下一个字符。
   • 如果不是退格符但skip_s大于0（当前不是#，但上一步检查到了#），则减少skip_s的值，并将索引 i 递减以跳过当前字符。
   • 如果既不是退格符且skip_s为0，则使用break跳出内层循环，准备进行字符比较或检查是否已处理完字符串 s 。
4. 处理字符串 t 中的退格符
   • 与处理字符串s的逻辑相同，但针对的是字符串 t 及其对应的索引 j 和计数器skip_t。
5. 字符比较
   • 在两个内层循环之后，如果 i 和 j 都大于等于0，则比较 s[ i ] 和 t[ j ] （只有在确定字符不需要被跳过时才会进行字符比较）。
   • 如果字符不相等，则返回false
6. 检查是否处理完字符串：
   • 如果 i 或 j 中的有一个仍然大于等于0（意味着一个字符串已经被完全处理，但另一个还没有），则这两个处理完的字符串肯定不相等，不需要后续处理，直接返回false。
7. 索引递减：
   • 在字符比较之后，递减 i 和 j 以准备检查下一个字符（如果需要跳过字符，则在循环内部就进行了递减）。
8. 返回值：
   • 如果前面步骤都没有报false，说明处理完 # 后两字符相等，返回true。

3.2 方法二实现

//定义辅助函数，用于重构字符串
char* rebuild(char* str){
    int n = strlen(str);
    int len = 0;
    char* ret = malloc(sizeof(char) * (n + 1)); //新建一个字符串，长度n+1是要留位置给结束位'\0'
    for(int i = 0; i < n; i++){
        if(str[i] != '#'){
        	//遍历到普通字符，则进栈，栈顶索引+1
            ret[len] = str[i];
            len++;
        }else if(str[i] == '#' && len > 0){
            //如果是退格符，且栈内有字符，则将栈顶索引-1，弹出栈顶字符
            //最终栈内不包含退格符和应该被删去的字符
            len--;
        }
    }
    ret[len] = '\0';//加入结束符
    return ret;//返回重构后的数组
}

bool backspaceCompare(char* s, char* t){
    //对s和t进行重构，得到的结果进行比较，但会比较结果true或false
    return strcmp(rebuild(s), rebuild(t)) == 0;
}

4. 总结

两种方法的时间复杂度都为O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度，都只需要遍历两字符串各一次。按自己能理解的方法去实现即可。