class Solution {
public:
bool backspaceCompare(string s, string t) {
}
};
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 <= 200s 和 t 只含有小写字母以及字符 '#'
进阶：
O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-11-17 17:00:11
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
def backspaceCompare2(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)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-11-17 16:59:38
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)
}
func backspaceCompare2(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
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.9 MB, 提交时间: 2023-11-17 16:58:30
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;
}
}
// 重构字符串
class Solution2 {
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();
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-11-17 16:57:34
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;
}
};
// 双指针，
class Solution2 {
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;
}
};
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-07-20 10:01:45
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
ls, lt = len(s), len(t)
arr1, arr2 = list(), list()
for i in range(ls):
if s[i] == '#' and len(arr1) > 0:
arr1 = arr1[:len(arr1)-1]
elif s[i] != '#':
arr1.append(s[i])
for i in range(lt):
if t[i] == '#' and len(arr2) > 0:
arr2 = arr2[:len(arr2)-1]
elif t[i] != '#':
arr2.append(t[i])
return ''.join(arr1) == ''.join(arr2)
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-30 10:46:05
func backspaceCompare(s string, t string) bool {
arr1, arr2 := []byte{}, []byte{}
n1, n2 := len(s), len(t)
for i := 0; i < n1; i++ {
if s[i] == '#' && len(arr1) > 0 {
arr1 = arr1[:len(arr1)-1]
} else if s[i] != '#' {
arr1 = append(arr1, s[i])
}
}
for i := 0; i < n2; i++ {
if t[i] == '#' && len(arr2) > 0 {
arr2 = arr2[:len(arr2)-1]
} else if t[i] != '#' {
arr2 = append(arr2, t[i])
}
}
return string(arr1) == string(arr2)
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-01 10:18:37
func backspaceCompare(s string, t string) bool {
arr1, arr2 := []byte{}, []byte{}
n1, n2 := len(s), len(t)
for i := 0; i < n1; i++ {
if s[i] == '#' && len(arr1) > 0 {
arr1 = arr1[:len(arr1)-1]
} else if s[i] != '#' {
arr1 = append(arr1, s[i])
}
}
for i := 0; i < n2; i++ {
if t[i] == '#' && len(arr2) > 0 {
arr2 = arr2[:len(arr2)-1]
} else if t[i] != '#' {
arr2 = append(arr2, t[i])
}
}
return string(arr1) == string(arr2)
}