Group Words by Letter Shift
Problem
A cipher tool shifts every letter of a word forward by the same amount, wrapping from z back to a, so "abc" can become "bcd" or "xyz". Given a list of lowercase words, group together the words that can be shifted into one another. Return the groups in the order their first word appears in the input, and keep the words inside each group in input order. There can be up to 10,000 words of up to 50 letters each.
Examples
Input: words = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
Output: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]]
Why: "az" shifted by one becomes "ba", since z wraps round to aInput: words = ["dog", "eph", "cat"]
Output: [["dog", "eph"], ["cat"]]Input: words = []
Output: []
Why: edge case, nothing to groupHints
0 / 3
Comparing every pair of words is quadratic. Group Anagrams avoided that by giving each word a key that every member of its group shares. What stays the same when you shift a word?
Shifting changes every letter but not the gap from one letter to the next. The gaps must wrap too, so measure them modulo 26.
Build a key from the gaps between neighbouring letters, (ord(b) - ord(a)) % 26 for each pair, and append the word to a dictionary list under that key. One-letter words all share the empty key.
Solution
Two words belong together exactly when the gaps between their neighbouring letters match, measured modulo 26 so that wrapping from z to a counts as a gap of one. That gap sequence is a canonical key, playing the role the sorted letters play in Group Anagrams, and a dictionary from key to list collects each group in one pass. Python dictionaries keep insertion order, which gives the groups in order of their first word. Time is O(total letters), and space is O(total letters) for the keys and groups.
def group_by_shift(words):
groups = {}
for w in words:
key = tuple((ord(b) - ord(a)) % 26 for a, b in zip(w, w[1:])) # wrap-aware gaps
groups.setdefault(key, []).append(w)
return list(groups.values())
print(group_by_shift(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]))
# -> [['abc', 'bcd', 'xyz'], ['acef'], ['az', 'ba'], ['a', 'z']]
print(group_by_shift(["dog", "eph", "cat"])) # -> [['dog', 'eph'], ['cat']]
print(group_by_shift([])) # -> []Stuck on the idea rather than the code? Group Anagrams covers it.