Leetcode 874 Solution

This article provides solution to leetcode question 874 (backspace-string-compare)
Categories:
Tags:
Access this page by simply typing in "lcs 874" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/backspace-string-compare

Solution

class Solution:
    def getNext(self, S, i):
        skip = 0
        while i >= 0:
            if S[i] == '#':
                skip += 1
                i -= 1
                continue

            if skip:
                skip -= 1
                i -= 1
            else:
                break
        return i

    def backspaceCompare(self, S: str, T: str) -> bool:
        i = len(S) - 1
        j = len(T) - 1

        while True:
            i = self.getNext(S, i)
            j = self.getNext(T, j)

            ch1 = S[i] if i >= 0 else None
            ch2 = T[j] if j >= 0 else None

            if ch1 != ch2:
                return False

            if i < 0 or j < 0:
                break

            i -= 1
            j -= 1

        return i == -1 and j == -1