pylist

844. Backspace String Compare

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.

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 <= S.length <= 200
1 <= 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?

Solution

Simulation Solution

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        return self.str2list(S) == self.str2list(T)
        
    def str2list(self, stri):
        ans = []
        for c in stri:
            if c == '#':
                if len(ans) > 0:
                    ans.pop()
            else:
                ans.append(c)
        return ans

Pointer Solution

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        i = len(S) - 1
        j = len(T) - 1
        while True:
            i = self.move_cursor(S, i)
            j = self.move_cursor(T, j)
            
            # Stop condition
            if min(i, j) < 0:
                if i < 0  and j < 0:
                    return True
                else:
                    return False
            
            # main logic
            if S[i] == T[j]:
                i -= 1
                j -= 1
                continue
            else: 
                return False
            
            
    def move_cursor(self, S, i):
        """
        move cursor i to the position of next char
        """
        n_sharp = 0
        while i >= 0:
            if S[i] == '#':
                n_sharp += 1
                i -= 1
                continue
            # S[i] != '#' :
            
            if n_sharp > 0:
                i -= 1
                n_sharp -= 1
                continue
            # n_sharp == 0 :
            
            break
        return i

Care