比较含退格的字符串 | LeetCode-844 | 双指针

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧!

---

LeetCode链接：844. 比较含退格的字符串

---

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.题解

2.1 暴力解法

class Solution {
    // 主方法 backspaceCompare，比较两个字符串 s 和 t 在处理退格字符 '#' 后是否相等
    public boolean backspaceCompare(String s, String t) {
        // 调用 getTrueString 方法获取处理退格后的字符串，并比较两者是否相等
        return getTrueString(s).equals(getTrueString(t));
        //字符串不能直接比较
        //return getTrueString(s) == getTrueString(t);//报错
    }

    // 辅助方法 getTrueString，用于处理包含退格字符 '#' 的字符串
    public String getTrueString(String s) {
        // 使用 StringBuilder sb 来构建处理退格后的有效字符串
        StringBuilder sb = new StringBuilder();
        
        // 遍历输入字符串 s 的每个字符
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);  // 获取当前字符
            
            // 如果当前字符不是 '#'，将其添加到 StringBuilder 中
            if (ch != '#') {
                sb.append(ch);
            } else {
                // 如果当前字符是 '#' 并且 sb 不为空，则删除 sb 中的最后一个字符，模拟退格操作
                if (sb.length() > 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        
        // 返回处理后的字符串
        return sb.toString();
    }
}

2.2 双指针

• 图解：https://leetcode.cn/problems/backspace-string-compare/solutions/1/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 使用双指针法
        // i 指针指向字符串 s 的最后一个字符
        // j 指针指向字符串 t 的最后一个字符
        int i = s.length() - 1;
        int j = t.length() - 1;
        // skipS 和 skipT 分别用于记录字符串 s 和 t 中的退格 '#' 的数量
        int skipS = 0, skipT = 0;

        // 当 i 或 j 任一大于等于 0 时，继续循环
        while (i >= 0 || j >= 0) {

            // 处理字符串 s 的退格
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    // 如果当前字符是 '#', 增加 skipS 计数，表示要跳过一个有效字符
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    // 如果当前字符不是 '#' 且 skipS 大于 0，表示前面有未处理的退格，需要跳过当前字符
                    skipS--;
                    i--;
                } else {
                    // 如果 skipS 为 0，且当前字符不是 '#', 说明找到了一个有效字符，退出循环
                    break;
                }
            }

            // 处理字符串 t 的退格
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    // 如果当前字符是 '#', 增加 skipT 计数，表示要跳过一个有效字符
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    // 如果当前字符不是 '#' 且 skipT 大于 0，表示前面有未处理的退格，需要跳过当前字符
                    skipT--;
                    j--;
                } else {
                    // 如果 skipT 为 0，且当前字符不是 '#', 说明找到了一个有效字符，退出循环
                    break;
                }
            }

            // 比较 s 和 t 中的当前字符
            if (i >= 0 && j >= 0) {
                // 如果当前 s 和 t 的字符不相同，返回 false
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                // 如果其中一个字符串已经处理完，而另一个没有，返回 false
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }

            // 继续向前移动 i 和 j
            i--;
            j--;
        }

        // 如果所有字符都相同，返回 true
        return true;
    }
}