Easy

题目描述

给定两个字符串 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) 的空间复杂度解决该问题吗？

解题思路

这个问题有两种主要解法：

方法一：栈模拟（直观解法）

最直观的想法是使用栈来模拟文本编辑器的行为。对于每个字符串：

  • 遇到普通字符就入栈
  • 遇到 # 就出栈（如果栈不为空）
  • 最后比较两个栈是否相等

这种方法时间复杂度 O(m+n)，空间复杂度 O(m+n)。

方法二：双指针从后往前遍历（最优解法）

为了达到 O(1) 的空间复杂度，我们可以从字符串末尾开始遍历。关键思路是：

  • 使用两个指针分别指向两个字符串的末尾
  • 用计数器记录需要跳过的字符数量（退格操作）
  • 从后往前找到下一个有效字符进行比较

具体步骤：

  1. 对于每个字符串，从后往前遍历
  2. 遇到 # 时，增加跳过计数
  3. 遇到普通字符时，如果有跳过计数就减少计数并继续，否则这就是有效字符
  4. 比较两个字符串当前的有效字符是否相同

这种方法巧妙地避免了额外的存储空间，实现了 O(1) 的空间复杂度。

代码实现

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            
            while (j >= 0) {
                if (t[j] == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            
            if (i >= 0 && j >= 0 && s[i] != t[j]) {
                return false;
            }
            if ((i >= 0) != (j >= 0)) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
};

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        skipS = skipT = 0
        
        while i >= 0 or j >= 0:
            while i >= 0:
                if s[i] == '#':
                    skipS += 1
                    i -= 1
                elif skipS > 0:
                    skipS -= 1
                    i -= 1
                else:
                    break
            
            while j >= 0:
                if t[j] == '#':
                    skipT += 1
                    j -= 1
                elif skipT > 0:
                    skipT -= 1
                    j -= 1
                else:
                    break
            
            if i >= 0 and j >= 0 and s[i] != t[j]:
                return False
            if (i >= 0) != (j >= 0):
                return False
            i -= 1
            j -= 1
        
        return True

public class Solution {
    public bool BackspaceCompare(string s, string t) {
        int i = s.Length - 1, j = t.Length - 1;
        int skipS = 0, skipT = 0;
        
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            
            while (j >= 0) {
                if (t[j] == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            
            if (i >= 0 && j >= 0 && s[i] != t[j]) {
                return false;
            }
            if ((i >= 0) != (j >= 0)) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    let i = s.length - 1;
    let j = t.length - 1;
    let skipS = 0;
    let skipT = 0;
    
    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (s[i] === '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        
        while (j >= 0) {
            if (t[j] === '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }
        
        if (i >= 0 && j >= 0 && s[i] !== t[j]) {
            return false;
        }
        
        if ((i >= 0) !== (j >= 0)) {
            return false;
        }
        
        i--;
        j--;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈方法双指针方法（推荐）
时间复杂度O(m + n)O(m + n)
空间复杂度O(m + n)O(1)

其中 m 和 n 分别是字符串 s 和 t 的长度。双指针方法在空间复杂度上有显著优势，满足进阶要求。

相关题目