跳转至

LeetCode: 844. 比较含退格的字符串

1、题目描述

给定 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”。


提示:

1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。

2、 解题思路

2.1 从后向前递推法

​ 因为字符串中仅包含退格键和小写字母,而退格键则是取消掉前面的一个字符,如果是多个退格键,则取消多个字符

​ 基本思路就是,从右面向左进行比较,判断出现去掉退格键的影响以后的第一个字符是什么,如果第一个字符相同,继续判断下一个

​ 直到出现不相同的或者字符串比较完毕,返回结果

char findFisrtCharForBackspaceString(char *s, int *length) {
    int backspaces = 0;
    char temp = 0;
    while (!temp && *length > 0) {
        if (s[*length - 1] == '#') {
            backspaces++;
            (*length)--;
        } else if (backspaces > 0) {
            (*length)--;
            backspaces--;
        } else if (*length >=1) {
            temp = s[*length - 1];
        } else {
            break;
        }
    }
    return temp;
}

bool backspaceCompare(char *S, char *T) {
    bool flag = true;
    int length_s = strlen(S);
    int length_t = strlen(T);


    while (length_s > 0 || length_t > 0) {
        if (findFisrtCharForBackspaceString(S, &length_s) != findFisrtCharForBackspaceString(T,&length_t)){
            flag = false;
            break;
        }
        length_s--;
        length_t--;
    }

    return flag;
}