unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 389. Find the Difference

link

Two passes

Lookup t‘s characters in s to find which one is extra.

Say len(s) = n.

Time: \mathcal{O}(n), space: \mathcal{O}(\texttt{alphabet-size}).

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s_map = {}
        for c in s:
            if c not in s_map:
                s_map[c] = 0
            s_map[c] += 1
        
        for c in t:
            if s_map.get(c, 0) == 0:
                return c
            s_map[c] -= 1

        return None

One pass

Note, XOR of same numbers is 0. Also, XOR is commutative. So, if we take XOR of all characters (as number) in both strings, we shall be left with the extra character.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        extra = ord(t[0])
        for a, b in zip(s, t[1:]):
            extra ^= ( ord(a) ^ ord(b) )
        
        return chr(extra)

tanvirdotzaman

,

Leave a comment