844. 比較含退格的字符串
給定 S 和 T 兩個字符串，當(dāng)它們分別被輸入到空白的文本編輯器后，判斷二者是否相等夺颤，并返回結(jié)果供汛。 # 代表退格字符枪汪。
示例 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”。
方法一：重構(gòu)字符串
在 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);
}
}
復(fù)雜度分析
時間復(fù)雜度：O(M + N)，其中 M, N是字符串 S 和 T 的長度越庇。
空間復(fù)雜度：O(M + N)罩锐。
方法二：雙指針
一個字符是否屬于最終字符串的一部分，取決于它后面有多少個退格符悦荒。
如果反向遍歷字符串唯欣，就可以先知道有多少個退格符，然后知道退格符左邊有多少個字符會被刪除搬味，對應(yīng)的也就知道哪些字符會保留在最終的字符串中境氢。
反向遍歷字符串，如果遍歷到一個退格符碰纬，那么再往左第一個非退格字符將會被刪除萍聊，剩余未被刪除的字符就是最終的字符串。
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;
}
}
復(fù)雜度分析
時間復(fù)雜度：O(M + N)悦析，其中 M, N 是字符串 S 和 T 的長度寿桨。
空間復(fù)雜度：O(1)。
