1.題目
給定 s 和 t 兩個(gè)字符串戳稽，當(dāng)它們分別被輸入到空白的文本編輯器后，如果兩者相等痹仙，返回 true 是尔。# 代表退格字符。
注意：如果對(duì)空文本輸入退格字符开仰，文本繼續(xù)為空拟枚。
示例 1：
輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會(huì)變成 "ac"薪铜。
示例 2：
輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會(huì)變成 ""。
示例 3：
輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會(huì)變成 "c"恩溅，但 t 仍然是 "b"隔箍。
提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小寫字母以及字符 '#'
進(jìn)階：
你可以用 O(n) 的時(shí)間復(fù)雜度和 O(1) 的空間復(fù)雜度解決該問題嗎？
2.思路
- 使用的方法:雙指針
- 思路
循環(huán)進(jìn)行判斷字符是不是‘#’ 脚乡。
如果不是 # 蜒滩，則將字符拼接成字符串。
如果是# 奶稠，則首先進(jìn)行判斷俯艰，拼接的字符串長(zhǎng)度是否為0，如果為0就不用進(jìn)行截取前面的字符了锌订，如果長(zhǎng)度不為0竹握，則進(jìn)行截取字符串，最后一位不要辆飘。最后判斷兩個(gè)拼接的字符串是否相等即可啦辐。
3.代碼
def backspaceCompare(s: String, t: String): Boolean = {
var sIndex = 0
var tIndex = 0
var str = ""
var ttr = ""
while (sIndex<s.length || tIndex<t.length){
if(sIndex<s.length){
if(s(sIndex)!='#') str = str+s(sIndex)
else {
if(str.length!=0) str = str.substring(0,str.length-1)
}
sIndex = sIndex+1
}
if(tIndex<t.length){
if(t(tIndex)!='#') ttr = ttr+t(tIndex)
else {
if(ttr.length!=0) ttr = ttr.substring(0,ttr.length-1)
}
tIndex = tIndex+1
}
}
return str.equals(ttr)
}
4.復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
