पाठ 6 / 26
Counting and Canonical Keys
यह पाठ अभी हिंदी में अनुवादित नहीं है, इसलिए अंग्रेज़ी में दिखाया जा रहा है।
Group things that are "the same".
लेखक: Rahul Agarwal · 15 साल से वेब डेवलपर
Counter and normalised keys
collections.Counter counts items and compares frequency profiles (anagrams have equal counters). To group equivalent items, map each to a canonical key: sorted letters for anagrams, a tuple of 26 letter counts for long words (O(k) instead of O(k log k)), or a normalised shape for islands. defaultdict(list) collects groups without key checks.
Grouping anagrams and counting letters, run
I ran this with Python 3.12.3 (standard library only). Words with the same sorted letters share a group; most_common returns the top counts, and equal counters identify anagrams.
# Group anagrams: a canonical key per group
from collections import Counter, defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(Counter("mississippi").most_common(2))
print(Counter("listen") == Counter("silent"))
Output:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[('i', 4), ('s', 4)]
TrueMention the alphabet assumption
A fixed 26-count array is O(1) space only if input is limited to lowercase English letters; say so.
त्वरित जाँच: What makes a good key for grouping anagrams?
- A random number
- The word length only
- The first letter
- The sorted letters of each word
Answer
The sorted letters of each word — Equivalent items share a key.