Words Equal Up to a Shift

Medium

To shift a word is to replace each of its letters with the next one in the alphabet, where z wraps around to a. For example, abc shifts to bcd, and xyz shifts to yza. A word can be shifted any number of times. Given a list of lowercase words words, group together the words that can be turned into one another by shifting, and return the list of groups. The order of the groups and the order of words inside a group do not matter. If a word appears several times, every occurrence goes into its group.

Example 1

words=["dog", "eph", "a", "q", "ace", "bdf"] → [['dog', 'eph'], ['a', 'q'], ['ace', 'bdf']]

Shifting dog by 1 gives eph; any one-letter word can be shifted into any other; ace shifts into bdf.

Example 2

words=["za", "ab", "ba"] → [['za', 'ab'], ['ba']]

Shifting za by 1 gives ab (after z comes a again). In ba the second letter comes before the first rather than after, so it gets its own group.

Constraints

1 ≤ len(words) ≤ 10⁴
1 ≤ len(words[i]) ≤ 50
words[i] consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String

Similar problems

Anagram Buckets Medium Split Into Dictionary Words Medium A Subsequence of One Word Only Medium Files With the Same Content Medium Highlight Search Hits Medium

Input

words=["dog", "eph", "a", "q", "ace", "bdf"]

Expected

[['dog', 'eph'], ['a', 'q'], ['ace', 'bdf']]

Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.