🥉844. 比较含退格的字符串@

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 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 <= 200
• 1 <= T.length <= 200
• S 和 T 只含有小写字母以及字符 ‘#’。

进阶：
你可以用的时间复杂度和的空间复杂度解决该问题吗？

题解

正常的写法没啥问题，不过进阶还有问题。而且不够简洁！js和Python用多了，很多栈的操作都默认是数组的操作了，反倒是说用栈解决还有点懵。

方法一、重构字符串

每次遍历到一个字符：

• 如果是退格符，将栈顶弹出；
  
• 如果是普通字符，将其压入栈中。

JavaScript

代码不够简洁！！

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function(S, T) {
    let s = S.split('')
    let t = T.split('')
    let stemp=[]
    let ttemp=[]
    for(let i=0;i<s.length;i++){
        if (s[i] === '#'){
            stemp.pop()
        } else {
            stemp.push(s[i])
        }
    }
    for(let i=0;i<t.length;i++){
        if (t[i] === '#'){
            ttemp.pop()
        } else {
            ttemp.push(t[i])
        }
    }
    return stemp.join('') === ttemp.join('')

};

Python

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)

复杂度分析

• 时间复杂度：，其中 N 和M 分别为字符串 S 和 T 的长度。需要遍历两字符串各一次。

• 空间复杂度：，其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。

双指针