LeetMotion
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.
count = [0] * 26. For each character c, increment count[ord(c) - ord("a")]. Since ord('a') = 97, subtracting it maps every lowercase letter to an index 0–25:'a'→0, 'b'→1, …, 'z'→25. Two strings that are anagrams always produce the identical26-tuple — this is O(k) per string, better than sorting's O(k log k).key = tuple(count). Then res[key].append(word) groups every anagram under the same bucket. Return list(res.values()). Total: O(m · k) time, O(m · k) space — the log factor is gone.The naive approach: for every string, compare it against every other string by sorting both and checking equality. Group matched strings together.
s, scan all other strings and sort both to check if they are anagrams.def groupAnagrams(strs): groups, used = [], [False] * len(strs) for i in range(len(strs)): if used[i]: continue group = [strs[i]] for j in range(i + 1, len(strs)): if sorted(strs[i]) == sorted(strs[j]): group.append(strs[j]); used[j] = True groups.append(group) return groups
Instead of sorting, we build a 26-element count array for each word — one slot per letter a–z. Each character c maps to slot ord(c) − ord('a') in O(1). Because there are only 26 lowercase letters, the entire count takes O(k) — no log factor. Two strings that are anagrams produce the identical 26-tuple, so we use tuple(count) as a hash map key.
res = defaultdict(list) and a fresh count = [0]*26 for each word.c in the word, do count[ord(c) − ord('a')] += 1.key = tuple(count). Append the word to res[key].strsord(char) − ord('a')m strings we iterate its k characters once. Each ord(c) − ord('a') lookup is O(1), so the entire count array fills in O(k). No sorting needed.m words: O(m).m = number of strings and k = maximum string length. Eliminates the log factor vs. sorting. Space is O(m · k) to store all words in the map.
Discussion
…