LC 0844 [E] Backspace String Compare - ALawliet/algorithms GitHub Wiki

O(s+t), O(s+t)

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def stack(string):
            st = []
            for char in string:
                if char != '#':
                    st.append(char)
                else:
                    if st:
                        st.pop()
            return st
                
        return stack(s) == stack(t)

O(n), O(1)

class Solution(object):
    def backspaceCompare(self, S1, S2):
        r1 = len(S1) - 1 
        r2 = len(S2) - 1
        
        while r1 >= 0 or r2 >= 0:
            char1 = char2 = ""
            if r1 >= 0:
                char1, r1 = self.getChar(S1, r1)
            if r2 >= 0:
                char2, r2 = self.getChar(S2, r2)
            if char1 != char2:
                return False
        return True
        
    
    def getChar(self, s , r):
        char, count = '', 0
        while r >= 0 and not char:
            if s[r] == '#':
                count += 1
            elif count == 0:
                char = s[r]
            else:
                count -= 1
            r -= 1
        return char, r

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:

        def getChar(s, i):
            skip_count = 0
            char = '' # set char as empty in case all characters are skipped
            
            while i>=0 and char=='': # if char is not empty, we will return it.
                if s[i]=='#':
                    skip_count += 1
                elif skip_count==0:
                    char = s[i]
                else:
                    skip_count -= 1
                
                i -= 1
            
            return char, i
        
        inds = len(s)-1
        indt = len(t)-1
        
        while inds>=0 or indt>=0:
            # chars = chart = ""
            # if inds>=0:
            chars, inds = getChar(s, inds)
            # if indt>=0:
            chart, indt = getChar(t, indt)
            
            if chars!=chart:
                return False
            
        return True

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i = len(s) - 1
        j = len(t) - 1
        count_i = 0
        count_j = 0
        while i >= 0 or j >= 0:
            if i >= 0:
                i = self.findValid(i, s)
            if j >= 0:
                j = self.findValid(j, t)
            if i>= 0 and j >= 0 and s[i] != t[j]:
                return False
            i -= 1
            j -= 1
        return i == j
    
    def findValid(self, idx, str):
        valid = False
        count = 0
        while idx >= 0 and not valid: 
            if str[idx] == "#":
                count += 1
                idx -= 1
            elif count == 0:
                valid = True
            else:
                count -= 1
                idx -= 1
        return idx

class Solution:
    def backspaceCompare(self, S1, S2):
        i1 = len(S1) - 1 
        i2 = len(S2) - 1
        
        while i1 >= 0 or i2 >= 0:
            c1 = ''
            c2 = ''
            if i1 >= 0:
                c1, i1 = self.nextValidChar(S1, i1)
            if i2 >= 0:
                c2, i2 = self.nextValidChar(S2, i2)
            if c1 != c2:
                return False
        return True
    
    def nextValidChar(self, s, i):
        char = ''
        count = 0
        while i >= 0 and not char:
            if s[i] == '#':
                count += 1
            elif count == 0:
                char = s[i]
            else:
                count -= 1
            i -= 1
        return char, i