Show problems as
Classic problem #249MediumArrayHash TableString

Group Shifted Strings

Real-world version: Dial Lock Families
Tracked in this browser only
Read Group Shifted Strings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An old cabinet is opened by a dial whose setting is written as a word of lowercase letters. Clicking the dial forward one notch advances every letter of the setting one step along the alphabet, and a letter sitting on z comes back round to a. One notch therefore takes the setting az to ba, and two notches take it to cb.

You are given strings, a list of settings found written on scraps of paper. Two settings belong to the same family when some number of notches, possibly zero, carries one of them to the other. A setting always shares a family with itself, and settings of different lengths can never share one.

Return the families as a list of lists. Every entry of strings must appear once in the answer, so a setting written on two scraps appears twice inside its family. The families may come back in any order, and so may the settings inside each family.

Examples

Example 1

Input
strings = ["az", "ba", "by", "cz"]
Output
[["az", "ba"], ["by", "cz"]]

One notch takes `az` to `ba`, so those two share a family. Turning `by` forward reaches `cz` only after 27 notches worth of movement on the first letter but 28 on the second, so no single number of notches links them and each stands alone.

Example 2

Input
strings = ["mno", "nop", "ab", "bc", "cd"]
Output
[["mno", "nop"], ["ab", "bc", "cd"]]

`mno` reaches `nop` in one notch. Among the two-letter settings, one notch takes `ab` to `bc` and another takes `bc` to `cd`, so all three sit in one family, which cannot include the three-letter settings.

Example 3

Input
strings = ["ab", "ac", "bc"]
Output
[["ab", "bc"], ["ac"]]

One notch carries `ab` to `bc`. No number of notches carries `ab` to `ac`, because the first letter would need one notch while the second would need two.

Constraints

  • 1 <= strings.length <= 200
  • 1 <= strings[i].length <= 50
  • strings[i] consists of lowercase English letters.

The groups you return, and the values inside each group, may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def group_strings(strings: list[str]) -> list[list[str]]:
Java
public List<List<String>> groupStrings(String[] strings)

More on the same topics