LC-0844 Easy LeetCode

844. Backspace String Compare

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 49% Topics: Two Pointers, String, Stack, Simulation

Reading material

Two Pointers 9 min Strings 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(m + n)
# Space: O(1)

import itertools


class Solution(object):
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def findNextChar(S):
            skip = 0
            for i in reversed(xrange(len(S))):
                if S[i] == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield S[i]

        return all(x == y for x, y in
                   itertools.izip_longest(findNextChar(S), findNextChar(T)))

Solution from kamyu104/LeetCode-Solutions · MIT