unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 242: Valid Anagram

link

Sort

Sorted, anagrams must be identical.

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

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        return all(a == b for a, b in zip(sorted(s), sorted(t)))

Character map

Every character of t must appear in s possibly in different order.

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

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        s_map = {}
        for c in s:
            s_map[c] = s_map.get(c, 0) + 1
        
        for c in t:
            if s_map.get(c, 0) == 0:
                return False
            s_map[c] -= 1
        
        return True

tanvirdotzaman

,

Leave a comment