

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

• LeetCode: 844. 比较含退格的字符串
  • 1、题目描述
  • 2、 解题思路
    • 2.1 从后向前递推法

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