Group Shifted Strings
Medium · hash map
Shifting a word by d places replaces every letter with the letter d places later in the alphabet, going back round to a after z. For example, shifting "abc" by 2 gives "cde", and shifting "xyz" by 3 gives "abc". A shift of 0 leaves the word unchanged.
Two words are in the same group if one can be turned into the other by shifting it by some number of places. Words of different lengths are never in the same group.
Given a list of lowercase words, split them into groups and return them as a list of lists.
- Inside a group, keep the words in the order they appear in
words(repeated words are kept every time). - Order the groups by the position of the first word of each group in
words.
Examples
Example 1
Input: words = ["abc", "bcd", "acf", "xyz", "az", "ba", "a", "z"]
Output: [["abc", "bcd", "xyz"], ["acf"], ["az", "ba"], ["a", "z"]]
abc, bcd and xyz are shifts of each other (xyz shifted by 3 is abc). az shifted by 1 is ba, and a shifted by 25 is z.
Example 2
Input: words = ["ab", "ab", "bc", "ac"]
Output: [["ab", "ab", "bc"], ["ac"]]
The repeated word ab is listed twice. ac has a different gap between its letters.
Example 3
Input: words = ["q"]
Output: [["q"]]
Constraints
- 1 <= len(words) <= 1000
- 1 <= len(words[i]) <= 100
- words[i] contains only lowercase English letters