PattySung

Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = “ab#c”, t = “ad#c” Output: true Explanation: Both s and t become “ac”. Example 2:

Input: s = “ab##”, t = “c#d#” Output: true Explanation: Both s and t become “”. Example 3:

Input: s = “a#c”, t = “b” Output: false Explanation: s becomes “c” while t becomes “b”.

<解題>


class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 初始化兩個指針，分別指向字符串的最後一個字符
        int s_pointer = s.length() - 1;
        int t_pointer = t.length() - 1;

        // 用於跟蹤要跳過的'#'的數量
        int s_skips = 0;
        int t_skips = 0;

        // 開始從字符串的末尾向前遍歷，進行比較
        while (s_pointer >= 0 || t_pointer >= 0) {

            // 在字符串s中處理退格字符
            while (s_pointer >= 0) {
                if (s.charAt(s_pointer) == '#') {
                    s_skips += 1;
                    s_pointer -= 1;
                } else if (s_skips > 0) {
                    s_pointer -= 1;
                    s_skips -= 1;
                } else {
                    break;
                }
            }

            // 在字符串t中處理退格字符
            while (t_pointer >= 0) {
                if (t.charAt(t_pointer) == '#') {
                    t_skips += 1;
                    t_pointer -= 1;
                } else if (t_skips > 0) {
                    t_pointer -= 1;
                    t_skips -= 1;
                } else {
                    break;
                }
            }

            // 如果兩個指針都仍然有效，且指向的字符不相等，返回false
            if (s_pointer >= 0 && t_pointer >= 0 && s.charAt(s_pointer) != t.charAt(t_pointer)) {
                return false;
            }

            // 如果其中一個指針有效，而另一個指針已經越界，返回false
            if ((s_pointer >= 0) != (t_pointer >= 0)) {
                return false;
            }

            // 向前移動兩個指針
            s_pointer -= 1;
            t_pointer -= 1;
        }

        // 如果遍歷完成後都沒有返回false，則表示經過退格操作後的字符串相等，返回true
        return true;
    }
}

Time: O(n) Space: O(1)

Leetcode-844. Backspace String Compare

<解題>