2020-04-10

[leetcode] Backspace String Compare - 30-Day LeetCoding Challenge Day 9

Question

Two string that might contain "#" are given. "#" means backspace, so the last letter before "#" is supposed to remove from the string. After all this operation, check if those two strings are equal or not.

844. Backspace String Compare

Solution

There are two ways to solve this. One way is that I check all elements from the left of the string and append it into a string. If I find "#", don't add it into the string and remove the last letter in the string. And, repeat this operation against two given string until the end of the string. Lastly, compare those string.

Time complexity of this solution is gonna be O(n + m) -> O(n), and space complexity is gonna be O(n + m) as well. It is brief but not efficient at thought of time. the next solution is better.

The second solution is that I check all elements from the right side while counting the number of "#" in the string. "#" means skipping the next letter when I reverse the string.

In actual code, I declare two-pointer to check all elements of both string and two integers to store the count of "#" at first. when the letter I am checking is not "#", the count should decrease. If the count is zero and the current letter is not "#", compare with the letter of another string. If those letters are not same, return false immediately. If all letters are correct, return True.

Submissions

Here is the result.

Runtime: 20 ms, faster than 98.37% of Python3 online submissions for Backspace String Compare.
Memory Usage: 13.7 MB, less than 8.00% of Python3 online submissions for Backspace String Compare.

Time complexity: O(n + m) -> O(n)
Space complexity: O(1)

I travel all elements once from the right side. So, time complexity is O(n). And two integers for counting "#" and two-pointer for checking all elements are constant. That is why space complexity is O(1).

Here is my python code.

def backspaceCompare(self, S: str, T: str) -> bool:
    bs: List[int] = [0, 0]
    s: int = len(S) - 1
    t: int = len(T) - 1
    while s > -1 or t > -1:
        while s > -1 and (S[s] == "#" or bs[0]):
            bs[0] += 1 if S[s] == "#" else -1
            s -= 1
        while t > -1 and (T[t] == "#" or bs[1]):
            bs[1] += 1 if T[t] == "#" else -1
            t -= 1
        if S[s] != T[t]:
            return False
        s -= 1
        t -= 1

    return True if s == t else False

Also, there is another approach. Here is the code from @awice in leetcode.

import itertools
def backspaceCompare(self, S: str, T: str) -> bool:
    def F(S):
        skip = 0
        for x in reversed(S):
            if x == '#':
                skip += 1
            elif skip:
                skip -= 1
            else:
                yield x

    return all(x == y for x, y in itertools.zip_longest(F(S), F(T)))

This code is really sophisticated. By using itertools.zip_longest, we can check each letter of the same index from two different string simultaneously. Unlike just zip statement, if the lengths of each string are uneven, the missing value is filled with None. It can change by setting the argument. Also, yield statement can suspend function's execution and retain that condition. we are enabled to resume it from the last condition when you run again. Therefore, this code works.