Formatted question description: https://leetcode.ca/all/844.html

844. Backspace String Compare (Easy)

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

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 = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

Solution 1.

Update the S and T to the results of applying backspaces, then compare the strings.

// OJ: https://leetcode.com/problems/backspace-string-compare/

// Time: O(N)
// Space: O(1)
class Solution {
    string normalize(string &s) {
        int len = 0;
        for (char c : s) {
            if (c == '#') len = max(len - 1, 0);
            else s[len++] = c;
        }
        s.resize(len);
        return s;
    }
public:
    bool backspaceCompare(string S, string T) {
        return normalize(S) == normalize(T);
    }
};

Solution 2.

If it’s not allowed to change the input string, we scan backward. back function is used to skip all characters that are deleted using backspaces. After back, the indexes are pointing to characters that we need to compare.

// OJ: https://leetcode.com/problems/backspace-string-compare/

// Time: O(N)
// Space: O(1)
class Solution {
    void back(string &s, int &i) {
        if (i < 0 || s[i] != '#') return;
        int cnt = 0;
        for (; i >= 0 && (cnt || s[i] == '#'); --i) {
            if (s[i] == '#') ++cnt;
            else --cnt;
        }
    }
public:
    bool backspaceCompare(string S, string T) {
        int i = S.size() - 1, j = T.size() - 1;
        while (i >= 0 || j >= 0) {
            back(S, i);
            back(T, j);
            if ((i >= 0 && j < 0) || (i < 0 && j >= 0)) return false;
            for (; i >= 0 && j >= 0 && S[i] != '#' && T[j] != '#'; --i, --j) {
                if (S[i] != T[j]) return false;
            } 
        }
        return true;
    }
};

Java

class Solution {
    public boolean backspaceCompare(String S, String T) {
        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();
        int length1 = S.length(), length2 = T.length();
        for (int i = 0; i < length1; i++) {
            char c = S.charAt(i);
            if (c == '#') {
                if (sb1.length() > 0)
                    sb1.deleteCharAt(sb1.length() - 1);
            } else
                sb1.append(c);
        }
        for (int i = 0; i < length2; i++) {
            char c = T.charAt(i);
            if (c == '#') {
                if (sb2.length() > 0)
                    sb2.deleteCharAt(sb2.length() - 1);
            } else
                sb2.append(c);
        }
        return sb1.toString().equals(sb2.toString());
    }
}

All Problems

All Solutions