844. 比较含退格的字符串

Posted on | In
Words count in article: 516 | Reading time ≈ 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 只含有小写字母以及字符 ‘#’。

解法

解法一：

使用栈，先入栈，碰到#就出栈

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean backspaceCompare(String S, String T) {
        return getRealString(S).equals(getRealString(T));
    }
	
	private String getRealString(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0;i < s.length();i++) {
			char c = s.charAt(i);
			if (c == '#' && !stack.isEmpty()) {
				stack.pop();
			} else if (c != '#') {
				stack.push(c);
			}
		}
		StringBuffer sb = new StringBuffer();
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		return sb.toString();
	}
}

解法二：

从字符串的尾部开始遍历，统计遇到的#符号个数记为count，当下一个字符不是#的时候，从该字符开始计算，跳过count个字符。当count为0，并且当前字符不为#时，才算作有效字符。

比如字符串123##22

当从字符串末尾开始遍历的时候，遇到了两个#，此时count为2，那么代表它要跳过两个字符，在跳过的同时，count自减。因此，当字符1的时候，count为0，那么1就是有效字符

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean backspaceCompare(String S, String T) {
		String s = getValidString(S);
		String t = getValidString(T);
		return s.equals(t);
	}

	private String getValidString(String S) {
		StringBuilder s = new StringBuilder();
		int count = 0;
		for (int i = S.length() - 1; i >= 0; i--)
			if (S.charAt(i) == '#') {
				count++;

			} else if (count > 0) {
				count--;
			} else {
				s.append(S.charAt(i));
			}

		return s.toString();
	}
0%