249. Group Shifted Strings π
Description
We can shift a string by shifting each of its letters to its successive letter.
- For example,
"abc"
can be shifted to be"bcd"
.
We can keep shifting the string to form a sequence.
- For example, we can keep shifting
"abc"
to form the sequence:"abc" -> "bcd" -> ... -> "xyz"
.
Given an array of strings strings
, group 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 |
|