動機

複習stack，但第二個解法很漂亮

Problem

Given two strings s and t, return true 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#cOutput: trueExplanation: Both s and t become ac.

Example 2:

Input: s = ab##, t = c#d#Output: trueExplanation: Both s and t become .

Example 3:

Input: s = a##c, t = #a#cOutput: trueExplanation: Both s and t become c.

Example 4:

Input: s = a#c, t = bOutput: falseExplanation: s becomes c while t becomes b.

 

Constraints:

  • 1 <= s.length, 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?

Sol

無腦stack

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        stk = []
        for c in s:
            if c == "#":
                if stk:
                    stk.pop()
            else:
                stk.append(c)
        s = ''.join(stk)
        
        stk = []
        for c in t:
            if c == "#":
                if stk:
                    stk.pop()
            else:
                stk.append(c)
        t = ''.join(stk)
        
        return s==t

有一個類似moore voting的手法

class Solution(object):
    def backspaceCompare(self, S, T):
        def F(S):
            skip = 0
            for x in reversed(S):
                if x == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield x

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