Leetcode-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”。

方法 ： 双指针

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

• 若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；

• 若该字符为普通字符：

  • 若 skip 为 0，则说明当前字符不需要删去；
  • 若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1;
        int j = T.length() - 1;

        // 记录退格的变量
        int skipS = 0;
        int skipT = 0;

        while(i >= 0 || j >= 0){
            // 处理字符串S
            while(i >= 0){
                if(S.charAt(i) == '#'){ //若该字符为退格符，则我们需要多删除一个普通字符，让skip 加1；
                    skipS++;
                    i--;
                }else if(skipS > 0){ // 若该字符为普通字符
                    //若skip不为0，则说明当前字符需要删去，让skip 减 1。同时向后退一格
                    skipS--;
                    i--;
                }else{
                    //skip 为 0，则说明当前字符不需要删去；
                    break;
                }
            }

            // 处理字符串T
            while(j >= 0){
                if(T.charAt(j) == '#'){ //若该字符为退格符，则我们需要多删除一个普通字符，让skip 加1；
                    skipT++;
                    j--;
                }else if(skipT > 0){
                    skipT--;
                    j--;
                }else{
                    break;
                }
            }

            if (i >= 0 && j >= 0) { // 退完格之后两字符串能够各自确定一个字符
                if (S.charAt(i) != T.charAt(j)) { // 然后将这两个字符进行比较
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) { // 遍历完字符串
                    return false;
                }
            }

            // 进入下一次循环
            i--;
            j--;
        }
        return true;
    }
}

打赏