844.比较含退格的字符串

发表于 | 分类于
字数统计: 399 | 阅读时长 ≈ 2

题目描述

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

示例 1：

1
2
3
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

示例 2：

1
2
3
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。

示例 3：

1
2
3
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：

1
2
3
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

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

题解

思路

  1. 分别将S和T入栈，遇到#出栈
  2. 比较两个栈内元素

C代码

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
bool backspaceCompare(char *S, char *T)
{
    int i, j;
    char stack1[200];int top1 = -1;
    char stack2[200];int top2 = -1;
    for (i = 0; i < strlen(S); i++)
    {
        if (S[i] == '#')
            top1 = top1 == -1 ? -1 : top1 - 1;
        else
            stack1[++top1] = S[i];
    }
    for (i = 0; i < strlen(T); i++)
    {
        if (T[i] == '#')
            top2 = top2 == -1 ? -1 : top2 - 1;
        else
            stack2[++top2] = T[i];
    }
    if (top1 != top2) return false;
    for (i = 0, j = 0; i <= top1, j <= top2; i++, j++)
        if (stack1[i] != stack2[j])
            return false;
    return true;
}

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        st1 = []
        st2 = []
        S = list(S)
        T = list(T)
        for s in S:
            if s == "#":
                if len(st1) != 0:
                    st1.pop()
                else:
                    continue
            else:
                st1.append(s)

        for t in T:
            if t == "#":
                if len(st2) != 0:
                    st2.pop()
                else:
                    continue
            else:
                st2.append(t)
        return str(st1) == str(st2)