给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,请你判断二者是否相等。# 代表退格字符。
如果相等,返回 true ;否则,返回 false 。
注意:如果对空文本输入退格字符,文本继续为空。
示例 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”。
提示:
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'
进阶:
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/backspace-string-compare
python
# 比较退格字符串
class Solution:
def backspaceStringCompare1(self, S: str, T: str) -> bool:
"""
栈的思想, 时间O(m+n),空间借助栈O(m+n)
:param S:
:param T:
:return:
"""
def buildNewString(s: str) -> str:
ret = list()
for ch in s:
if ch != '#':
ret.append(ch)
elif ret:
ret.pop()
return "".join(ret)
return buildNewString(S) == buildNewString(T)
def backspaceStringCompare(self, S: str, T: str) -> bool:
"""
双指针,时间O(m+n) 空间O(1)
:param S:
:param T:
:return:
"""
skips,skipt = 0, 0
i, j = len(S)-1, len(T)-1
while True:
# 右向左,rm S的#
while i >= 0:
if S[i] == '#': # 遇到#,skip++
skips += 1
else: #遇到非#字符
if skips > 0:
skips -= 1 #之前遇到# skip--
else: # skip = 0, break, 此时为字符
break
i -= 1
# 右向左,rm T的#
while j >= 0:
if T[j] == '#':
skipt += 1
else:
if skipt > 0:
skipt -= 1
else:
break
j -= 1
# 此处,#已经消完 比较对应字符
if i < 0 or j < 0:
break
if S[i] != T[j]:
return False
i -= 1
j -= 1
if i == -1 and j == -1:
return True
return False
if __name__ == "__main__":
s = '#w#e#abc'
t = '###v#abc'
test = Solution()
print(test.backspaceStringCompare(s,t))
golang
//+build ignore
package main
import "fmt"
func man() {
var s string = "#w#e#abc"
var t string = "###v#abc"
fmt.Println(backspaceStringCompare(s, t))
}
// 借助栈,空间O(m+n)
func backspaceStringCompare(s string, t string) bool {
return buildNewString(s) == buildNewString(t)
}
func buildNewString(s string) string {
ret := []rune{}
for _, v := range s {
if v != '#' {
ret = append(ret, v) // push
} else if len(ret) > 0 {
ret = ret[:len(ret)-1] // pop
}
}
return string(ret)
}