844. 比较含退格的字符串
给定 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”。
方法一：重构字符串
在 build(S) 中，使用栈存储每次输入的字符。
class Solution {
public boolean backspaceCompare(String S, String T) {
return build(S).equals(build(T));
}
public String build(String S) {
Stack<Character> ans = new Stack();
for (char c: S.toCharArray()) {
if (c != '#')
ans.push(c);
else if (!ans.empty())
ans.pop();
}
return String.valueOf(ans);
}
}
复杂度分析
时间复杂度：O(M + N)，其中 M, N是字符串 S 和 T 的长度。
空间复杂度：O(M + N)。
方法二：双指针
一个字符是否属于最终字符串的一部分，取决于它后面有多少个退格符。
如果反向遍历字符串，就可以先知道有多少个退格符，然后知道退格符左边有多少个字符会被删除，对应的也就知道哪些字符会保留在最终的字符串中。
反向遍历字符串，如果遍历到一个退格符，那么再往左第一个非退格字符将会被删除，剩余未被删除的字符就是最终的字符串。
class Solution {
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
while (i >= 0) { // Find position of next possible char in build(S)
if (S.charAt(i) == '#') {skipS++; i--;}
else if (skipS > 0) {skipS--; i--;}
else break;
}
while (j >= 0) { // Find position of next possible char in build(T)
if (T.charAt(j) == '#') {skipT++; j--;}
else if (skipT > 0) {skipT--; j--;}
else break;
}
// If two actual characters are different
if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
return false;
// If expecting to compare char vs nothing
if ((i >= 0) != (j >= 0))
return false;
i--; j--;
}
return true;
}
}
复杂度分析
时间复杂度：O(M + N)，其中 M, N 是字符串 S 和 T 的长度。
空间复杂度：O(1)。
