249. Group Shifted Strings π
Description
Perform the following shift operations on a string:
- Right shift: Replace every letter with the successive letter of the English alphabet, where 'z' is replaced by 'a'. For example,
"abc"
can be right-shifted to"bcd"
or"xyz"
can be right-shifted to"yza"
. - Left shift: Replace every letter with the preceding letter of the English alphabet, where 'a' is replaced by 'z'. For example,
"bcd"
can be left-shifted to"abc" or
"yza"
can be left-shifted to"xyz"
.
We can keep shifting the string in both directions to form an endless shifting sequence.
- For example, shift
"abc"
to form the sequence:... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> ...
.<-> "zab" <-> "abc" <-> ...
You are given an array of strings strings
, group together all strings[i]
that belong to the same shifting sequence. You may return the answer in any order.
Example 1:
Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]
Example 2:
Input: strings = ["a"]
Output: [["a"]]
Constraints:
1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i]
consists of lowercase English letters.
Solutions
Solution 1: Hash Table
We use a hash table $g$ to store each string after shifting and with the first character as 'a
'. That is, $g[t]$ represents the set of all strings that become $t$ after shifting.
We iterate through each string. For each string, we calculate its shifted string $t$, and then add it to $g[t]$.
Finally, we take out all the values in $g$, which is the answer.
The time complexity is $O(L)$ and the space complexity is $O(L)$, where $L$ is the sum of the lengths of all strings.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|