Group strings by a common letter shift

Question

Two lowercase strings belong to the same shift group if you can turn one into the other by shifting every letter forward by the same amount, wrapping around from z back to a. So "abc", "bcd", and "xyz" are all in one group, and "az", "ba" are in another (a+1 = b, z+1 = a).

words = ["abc", "bcd", "xyz", "az", "ba", "acd"]
-> [["abc", "bcd", "xyz"], ["az", "ba"], ["acd"]]

Group the strings. Aim for linear time in total characters.

Accepted Answer

The shift changes every letter by the same amount, so the gaps between consecutive letters are what stay fixed. A clean canonical form: shift each word so it starts at a, by subtracting the first letter's code from every letter, taking the result modulo 26. Then "abc" becomes offsets (0, 1, 2) and so does "bcd" and "xyz"; "az" becomes (0, 25) and so does "ba" (from b to a is -1, which is 25 mod 26). Bucket by this tuple. On the example, abc, bcd, xyz all key to (0, 1, 2), az, ba both key to (0, 25), and acd keys to (0, 2, 3) alone, giving the three groups. Each key costs one pass over the wor…

Group strings by a common letter shift

Your answer

More Coding questions