1.题目
给定 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 <= 200
s 和 t 只含有小写字母以及字符 '#'
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
2.思路
- 使用的方法:双指针
- 思路
循环进行判断字符是不是‘#’ 。
如果不是 # ，则将字符拼接成字符串。
如果是# ，则首先进行判断，拼接的字符串长度是否为0，如果为0就不用进行截取前面的字符了，如果长度不为0，则进行截取字符串，最后一位不要。最后判断两个拼接的字符串是否相等即可。
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.复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
