844

844. Backspace String Compare (Easy)

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".

 

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

 

Follow up: Can you solve it in O(n) time and O(1) space?

Companies: Goldman Sachs, Google, Oracle, Grammarly, Microsoft, IBM, Amazon, Booking.com, Apple, Visa, Bloomberg, VMware, Twilio, TikTok

Related Topics:
Two Pointers, String, Stack, Simulation

Similar Questions:

• Crawler Log Folder (Easy)
• Removing Stars From a String (Medium)

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    void back(string &s, int &i) {
        int cnt = 0;
        while (i >= 0 && (s[i] == '#' || cnt)) {
            cnt += s[i--] == '#' ? 1 : -1;
        }
    }
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;
    }
};