Google 844. Backspace String Compare

Google Interview 844. Backspace String Compare

Given two strings s and t, return True if they are equal. ‘#’ means backspace.

Examples

• Input: s = “ab#c”, t = “ad#c”
• Output: true
• Explanation: Both s and t become “ac”.

• Input: s = “abb#c”, t = “ade#c”
• Output: false
• Explanation: s becomes “abc” and t becomes “adc”.

Python 3 Solution

Solution 1: use a list to implement a stack. append adds an item and pop removes it.

Test code

def main():
    print("start")

    s = "ab#c"
    t = "ad#c"

    print ("s: " + s)
    print ("t: " + t)
    
    sol = Solution()
    result = sol.backspaceCompare(s,t)
    print("result is: "+ str(result))

    print("end")
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def sb(chars):
            stack = []
            for char in chars:
                #print("- loop char: "+ str(char))
                if char != "#":
                    stack.append(char)
                    #print("--+ loop stack append: "+ str(stack))
                elif len(stack) != 0:
                    stack.pop()
                    #print("--- loop stack pop: "+ str(stack))
            return "".join(stack)
        
        return sb(s) == sb(t)
    
  

if __name__ == "__main__":
    main()

Test Output

start
s: ab#c
t: ad#c
- loop char: a
--+ loop stack append: ['a']
- loop char: b
--+ loop stack append: ['a', 'b']
- loop char: #
--- loop stack pop: ['a']
- loop char: c
--+ loop stack append: ['a', 'c']
- loop char: a
--+ loop stack append: ['a']
- loop char: d
--+ loop stack append: ['a', 'd']
- loop char: #
--- loop stack pop: ['a']
- loop char: c
--+ loop stack append: ['a', 'c']
result is: True
end
>>>

Final Solution

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def sb(chars):
            stack = []
            for char in chars:
                if char != "#":
                    stack.append(char)
                elif len(stack) != 0:
                    stack.pop()
            return "".join(stack)
       
        return sb(s) == sb(t)