844. 比较含退格的字符串

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 <= 200
s 和 t 只含有小写字母以及字符 ‘#’

进阶：

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解法一：(数组模拟栈)

        var backspaceCompare = function (s, t) {
            let sArr = [];
            let tArr = [];

            // 分别遍历两个字符串，如果当前字符串不是#，那就push进数组中，否则就从数组中pop一个元素
            for (let i of s) {
                if (i == '#') {
                    sArr.pop();
                }else{
                    sArr.push(i);
                }
            }
            for (let i of t) {
                if (i == '#') {
                    tArr.pop();
                }else{
                    tArr.push(i);
                }
            }
            // 最后判断数组中的元素是否相等，如果有一个不等那就返回false
            while(sArr.length!==0&&tArr.length!==0) {
                if (sArr.pop()!== tArr.pop()) {
                    return false;
                }
            }
            // pop完毕后看两个数组是否相等，如果相等则说明数组中没有元素，返回true，否则返回fasle
            return sArr.length===tArr.length?true:false;
        };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解法二

        var backspaceCompare = function (s, t) {
            // 使用字符串保存
            let sArr = "";
            let tArr = "";

            // 遍历s和t，如果遇到#，就去掉sArr或tArr中的最后一位
            for (let i of s) {
                if (i == '#') {
                    sArr = sArr.slice(0,-1);
                }else{
                    sArr += i;
                }
            }
            for (let i of t) {
                if (i == '#') {
                    tArr = tArr.slice(0,-1);
                }else{
                    tArr += i;
                }
            }
            
            // 最后直接比较两个字符串是否相同，不用逐个判断
            if(sArr===tArr){
                return true;
            }else{
                return false;
            }
        };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28