LC844.md

Problem: Backspace String Compare

Difficulty: Easy

Description:

Given two strings S and T, return 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.

Examples:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Constraints:

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

Solutions:

To solve this problem we can use define a helper function to preprocess each string and apply the escape character. At the end if the preprocessed strings are the same, we return True. The time and space complexity is O(N + M) where N is the length of S and M is the lenght of T.

def backspaceCompare(S, T):
    """
    :type S: str
    :type T: str
    :rtype: bool
    :Time Complexity: O(N + M)
    :Space Complexity: O(N + M)
    """

    def helper(word):
        seen = []
        for char in word:
            if char == "#":
                if len(seen) > 0:
                    seen.pop()
            else:
                seen.append(char)

        return "".join(seen)

    return True if helper(S) == helper(T) else False