力扣(LeetCode)844. 比较含退格的字符串(C语言)

一、环境说明

1. 本文是 LeetCode 844题 : 比较含退格的字符串，使用c语言实现。
2. 双指针，模拟字符串退格。
3. 测试环境:Visual Studio 2019。

二、代码展示

bool backspaceCompare(char * s, char * t){
    int i = strlen(s)-1,j = strlen(t) - 1;//i指向s，j指向t,从右往左
    int skipS = 0,skipT = 0;//初始#数量为0
    while(i>=0||j>=0){//用||表示，只要有一方没遍历完，就参与循环体内的判断。如果能遍历完，return true，不能遍历完，return false
        while(i>=0){//考虑s
            if('#'==s[i]){//遇到#
                skipS++;
                i--;
            }else if(skipS>0){//遇到字母,有未使用的#
                skipS--;
                i--;
            }else{//遇到字母,#用完了
                break;
            }
        }
        while(j>=0){//考虑t
            if('#'==t[j]){//遇到#
                skipT++;
                j--;
            }else if(skipT>0){//遇到字母,有未使用的#
                skipT--;
                j--;
            }else{//遇到字母,#用完了
                break;
            }
        }
        if(i>=0&&j>=0){//有剩余字母
            if(s[i]!=t[j]){//当前首字母不同
                return false;//字符串不同
            }
        }else{//至少有一方遍历完毕(i<0||j<0)
            if(i>=0||j>=0){//有一方没有遍历完毕。()
                return false;
            }
            //如果双方都遍历完毕，下一次循环，就跳出了。return true
        }
        i--,j--;
    }
    return true;//双方均遍历完毕
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

三、思路分析

• 两种做法

1. 栈，后入先出，遇到字母入栈，遇到#，栈顶出栈
2. 双指针，同时从右往左遍历s和t，i指s，j指t。

• 我们使用方法2.双指针

1. 设置$skipS$和$skipT$,代表当前#的数量,
2. 如果遇到字母,$skip=0$,则比较$s$和$t$的首字母，如果一方有字母，另一方遍历完毕，return false;
3. 如果遇到$\#$，$skip$++;
4. 如果遇到字母，且$skip>0$,$skip$–,遍历位置–。
5. 只有双方同时遍历完毕,return true。

四、代码分析

• 理解思路很重要！
• 欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(n+m)$ ,$n$是$s$的长度，$m$是$t$的长度，同时遍历字符串$s、t$的时间复杂度是$O(n+m)$。
2. 空间复杂度:$O(1)$,除若干变量使用的常量空间，没有额外使用线性空间。