LC 49 & LC 242 & LC 383

Solution to LeetCode 49 Group Anagrams, LeetCode 242 Valid Anagram, and LeetCode 383 Ransom Note.

LeetCode 49

Group Anagrams. (Medium) [link]

1] Use the sorted string as the key of the HashTable. Time complexity O(nklogk) where n is the number of strings and k is the length of the string. Space complexity O(nk).

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        HashTable = collections.defaultdict(list)
        for i in strs:
              key = "".join(sorted(i))
            HashTable[key].append(i)

        return list(HashTable.values())

2] Use the dictionary as the key of the HashTable. Time complexity O(n(k+26)). Space complexity O(n(k+26)).

Note that list is mutable. Tuple and string are immutable. A dictionary key must be of a type that is immutable.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        HashTable = collections.defaultdict(list)
        for i in strs:
            MAP = [0] * 26
            for le in i:
                key = ord(le)-ord('a')
                MAP[key] += 1
            
            HashTable[tuple(MAP)].append(i)
        return list(HashTable.values())

LeetCode 242

Valid Anagram (Easy) [link]

1] Brute Force Solution. Time complexity O(nlogn). Space complexity O(1).

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s = sorted(s)
        t = sorted(t)
        for i in range(len(s)):
            if s[i] != t[i]:
                return False

        return True

2] HashTable by an array. Time complexity O(n). Space complexity O(1).

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        HashTable = [0] * 26
        for i in range(len(s)):
            HashTable[ord(s[i]) - ord('a')] += 1
        for j in range(len(t)):
            HashTable[ord(t[j]) - ord('a')] -= 1
        for q in range(26):
            if HashTable[q] != 0:
                return False

        return True

3] HashTable by a dictionary. Time complexity O(n). Space complexity O(1).

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_dict = collections.defaultdict(int)
        t_dict = collections.defaultdict(int)

        for i in s:
            s_dict[i] += 1
        for j in t:
            t_dict[j] += 1

        return s_dict == t_dict

LeetCode 383

Ransom Note (Easy) [link]

1] HashTable. Time complexity O(n). Space complexity O(1).

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        HashTable = [0] * 26
        for i in range(len(magazine)):
            HashTable[ord(magazine[i]) - ord('a')] += 1
        for j in range(len(ransomNote)):
            HashTable[ord(ransomNote[j]) - ord('a')] -= 1
        print(HashTable)
        for q in range(len(HashTable)):
            if HashTable[q] < 0:
                return False

        return True