algoadvance

Leetcode 844. Backspace String Compare

Problem Statement

Leetcode Problem 844: Backspace String Compare

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

Clarifying Questions

1. What characters can the strings contain besides #?
   • The strings will contain lowercase letters and the # character.
2. Is the comparison case-sensitive?
   • Yes, the comparison is case-sensitive.
3. What is the maximum length for the strings s and t?
   • Both strings can have lengths up to 200.

Strategy

We can solve this problem efficiently using a two-pointer approach working from the end of both strings towards the beginning:

1. Iterate backward through strings s and t:
   • Use pointers to iterate backwards through both strings.
   • Skip characters when a # is encountered and adjust pointers appropriately to account for backspaces.
2. Character Comparison:
   • Compare the non-backspaced versions of s and t by iterating over them from the end to the beginning.
   • If at any point the characters being compared are different, return false.
   • If all characters match, return true.

This approach avoids explicitly building the final strings, thus optimizing space and time complexities.

Code

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            // Process backspaces in s
            while (i >= 0) {
                if (s[i] == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }

            // Process backspaces in t
            while (j >= 0) {
                if (t[j] == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            if (i >= 0 && j >= 0 && s[i] != t[j]) {
                return false;
            }

            // If one string is finished and the other isn't, they aren't equal
            if ((i >= 0) != (j >= 0)) {
                return false;
            }

            i--;
            j--;
        }

        return true;
    }
};

Time Complexity

• Time Complexity: O(n + m) where n and m are the lengths of strings s and t respectively. In the worst case, each character in the strings is processed once.

• Space Complexity: O(1) because we are using a constant amount of additional space for the pointers and skip counters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?