给定 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 <= 200s 和 t 只含有小写字母以及字符 '#'
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
方法一：重构字符串 思路及算法
最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
如果它是退格符，那么我们将栈顶弹出；
如果它是普通字符，那么我们将其压入栈中。
代码
[sol1-C++] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : bool backspaceCompare (string S, string T) return build (S) == build (T); } string build (string str) { string ret; for (char ch : str) { if (ch != '#' ) { ret.push_back (ch); } else if (!ret.empty ()) { ret.pop_back (); } } return ret; } };
[sol1-Java] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean backspaceCompare (String S, String T) { return build(S).equals(build(T)); } public String build (String str) { StringBuffer ret = new StringBuffer (); int length = str.length(); for (int i = 0 ; i < length; ++i) { char ch = str.charAt(i); if (ch != '#' ) { ret.append(ch); } else { if (ret.length() > 0 ) { ret.deleteCharAt(ret.length() - 1 ); } } } return ret.toString(); } }
[sol1-Golang] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 func build (str string ) string { s := []byte {} for i := range str { if str[i] != '#' { s = append (s, str[i]) } else if len (s) > 0 { s = s[:len (s)-1 ] } } return string (s) } func backspaceCompare (s, t string ) bool { return build(s) == build(t) }
[sol1-Python3] 1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def backspaceCompare (self, S: str , T: str ) -> bool : def build (s: str ) -> str : ret = list () for ch in s: if ch != "#" : ret.append(ch) elif ret: ret.pop() return "" .join(ret) return build(S) == build(T)
[sol1-C] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 char * build (char * str) { int n = strlen (str), len = 0 ; char * ret = malloc (sizeof (char ) * (n + 1 )); for (int i = 0 ; i < n; i++) { if (str[i] != '#' ) { ret[len++] = str[i]; } else if (len > 0 ) { len--; } } ret[len] = '\0' ; return ret; } bool backspaceCompare (char * S, char * T) { return strcmp (build(S), build(T)) == 0 ; }
复杂度分析
方法二：双指针 思路及算法
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
代码
[sol2-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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution {public : bool 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 (i >= 0 ) { if (S[i] == '#' ) { skipS++, i--; } else if (skipS > 0 ) { skipS--, i--; } else { break ; } } while (j >= 0 ) { if (T[j] == '#' ) { skipT++, j--; } else if (skipT > 0 ) { skipT--, j--; } else { break ; } } if (i >= 0 && j >= 0 ) { if (S[i] != T[j]) { return false ; } } else { if (i >= 0 || j >= 0 ) { return false ; } } i--, j--; } return true ; } };
[sol2-Java] 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 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 (i >= 0 ) { if (S.charAt(i) == '#' ) { skipS++; i--; } else if (skipS > 0 ) { skipS--; i--; } else { break ; } } while (j >= 0 ) { if (T.charAt(j) == '#' ) { skipT++; j--; } else if (skipT > 0 ) { skipT--; j--; } else { break ; } } if (i >= 0 && j >= 0 ) { if (S.charAt(i) != T.charAt(j)) { return false ; } } else { if (i >= 0 || j >= 0 ) { return false ; } } i--; j--; } return true ; } }
[sol2-Golang] 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 func backspaceCompare (s, t string ) bool { skipS, skipT := 0 , 0 i, j := len (s)-1 , len (t)-1 for i >= 0 || j >= 0 { for i >= 0 { if s[i] == '#' { skipS++ i-- } else if skipS > 0 { skipS-- i-- } else { break } } for j >= 0 { if t[j] == '#' { skipT++ j-- } else if skipT > 0 { skipT-- j-- } else { break } } if i >= 0 && j >= 0 { if s[i] != t[j] { return false } } else if i >= 0 || j >= 0 { return false } i-- j-- } return true }
[sol2-Python3] 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 class Solution : def backspaceCompare (self, S: str , T: str ) -> bool : i, j = len (S) - 1 , len (T) - 1 skipS = skipT = 0 while i >= 0 or j >= 0 : while i >= 0 : if S[i] == "#" : skipS += 1 i -= 1 elif skipS > 0 : skipS -= 1 i -= 1 else : break while j >= 0 : if T[j] == "#" : skipT += 1 j -= 1 elif skipT > 0 : skipT -= 1 j -= 1 else : break if i >= 0 and j >= 0 : if S[i] != T[j]: return False elif i >= 0 or j >= 0 : return False i -= 1 j -= 1 return True
[sol2-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 26 27 28 29 30 31 32 33 34 35 36 bool backspaceCompare (char * S, char * T) { int i = strlen (S) - 1 , j = strlen (T) - 1 ; int skipS = 0 , skipT = 0 ; while (i >= 0 || j >= 0 ) { while (i >= 0 ) { if (S[i] == '#' ) { skipS++, i--; } else if (skipS > 0 ) { skipS--, i--; } else { break ; } } while (j >= 0 ) { if (T[j] == '#' ) { skipT++, j--; } else if (skipT > 0 ) { skipT--, j--; } else { break ; } } if (i >= 0 && j >= 0 ) { if (S[i] != T[j]) { return false ; } } else { if (i >= 0 || j >= 0 ) { return false ; } } i--, j--; } return true ; }
复杂度分析
