一【题目类别】

• 栈

二【题目难度】

• 简单

三【题目编号】

• 844.比较含退格的字符串

四【题目描述】

• 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
• 注意：如果对空文本输入退格字符，文本继续为空。

五【题目示例】

• 示例 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 = “b”
  • 输出：false
  • 解释：s 会变成 “c”，但 t 仍然是 “b”。

六【题目提示】

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 ‘#’

七【题目进阶】

• 进阶：你可以用 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度解决该问题吗？

八【解题思路】

• 利用栈的思想
• 遇到不是‘#’就入栈
• 遇到‘#’如果栈不空就退栈，如果栈空不进行操作
• 最后先比较栈长度，如果长度不相同肯定不是相同的字符串
• 然后一一比较栈元素，如果有不相同的肯定也不是相同的字符串
• 如果都没问题就是相同的字符串

九【时间频度】

• 时间复杂度：$O(n)$，其中 $n$ 是数组元素个数
• 空间复杂度：C语言为$O(1)$，Java语言为$O(n)$，其中 $n$ 是数组元素个数

十【代码实现】

1. Java语言版

package Stack;

import java.util.Stack;

public class p844_CompareStringsWithBackspaces {

    public static void main(String[] args) {
        String s = "ab#c";
        String t = "ad#c";
        boolean res = backspaceCompare(s, t);
        System.out.println("res = " + res);
    }

    public static boolean backspaceCompare(String s, String t) {
        Stack stackS = new Stack();
        Stack stackT = new Stack();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '#') {
                stackS.push(s.charAt(i));
            } else {
                if (!stackS.isEmpty()) {
                    stackS.pop();
                } else {
                    continue;
                }
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) != '#') {
                stackT.push(t.charAt(i));
            } else {
                if (!stackT.isEmpty()) {
                    stackT.pop();
                } else {
                    continue;
                }
            }
        }
        if (stackS.size() != stackT.size()) {
            return false;
        } else {
            while (!stackS.isEmpty()) {
                if (stackS.pop() != stackT.pop()) {
                    return false;
                }
            }
        }
        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
41
42
43
44
45
46
47
48
49
50
51

2. C语言版

#include
#include

bool backspaceCompare(char * s, char * t)
{
	int topS = -1;
	int topT = -1;
	for (int i = 0; i < strlen(s); i++)
	{
		if (s[i] != '#')
		{
			s[++topS] = s[i];
		}
		else
		{
			if (topS != -1)
			{
				topS--;
			}
			else
			{
				topS = -1;
			}
		}
	}
	for (int i = 0; i < strlen(t); i++)
	{
		if (t[i] != '#')
		{
			t[++topT] = t[i];
		}
		else
		{
			if (topT != -1)
			{
				topT--;
			}
			else
			{
				topT = -1;
			}
		}
	}
	if (topS != topT)
	{
		return false;
	}
	else
	{
		for (int i = 0; i <= topS; i++)
		{
			if (s[i] != t[i])
			{
				return false;
			}
		}
	}
	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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

十一【提交结果】

1. Java语言版
   

2. C语言版