🌕 844. 比较含退格的字符串

难度: 🌕

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 思路：
        // 双指针 - 从后往前遍历
        int m = s.length();
        int n = t.length();
        int i = m - 1;
        int j = n - 1;
        while(i >= 0 && j >= 0) {
            i = mySol(s, i);
            // System.out.println("i : " + i);
            j = mySol(t, j);
            // System.out.println("j : " + j);
            if(i < 0 || j < 0) {
                break;
            }
            if(s.charAt(i) == t.charAt(j)) {
                i --;
                j --;
            } else {
                return false;
            }
        }
        // 防止一方已经遍历完毕，另一方虽然没有遍历完，但剩下的元素也可以互相抵消
        if(i >= 0) {
            i = mySol(s, i);
        }
        if(j >= 0) {
            j = mySol(t, j);
        }
        if(i < 0 && j < 0) {
            return true;
        } else {
            return false;
        }
    }

    private int mySol(String str, int from) {
        if(str.charAt(from) != '#') {
            return from;
        }
        // == '#'
        int count = 0;
        int cur = from;
        while(cur >= 0 && str.charAt(cur) == '#') {
            count ++;
            cur --;
        }
        if(cur < 0) {
            return cur;
        }
        // cur >= 0
        // [cur] != '#'
        // 往前删除 count 个非 '#' 字符
        while(cur >= 0 && count > 0) {
            if(str.charAt(cur) == '#') {
                count ++;
                cur --;
            } else {
                count --;
                cur --;
            }
        }
        if(cur < 0) {
            return cur;
        }
        // cur >= 0
        // 判断 cur 处是否还是 '#'，若是，继续往前删除
        return mySol(str, cur);
    }
}

---

输出