Loading page…
Practice problem · medium
A search engine stores keywords with a simple cipher. To hide a keyword, a tool moves every letter forward by the same number of places in the alphabet, and z wraps around to a. So abc becomes bcd with a shift of 1.
You get a list of stored keys. You must group the keys that are shifts of one another, so the analysts can review each family of keys together.
Write group_shifted(keys).
keys[i] is the i-th stored key.Input: keys = ["abc", "bcd", "az", "ba", "xyz"]
Output: [[0, 1, 4], [2, 3]]The trace gives each key a canonical form: the distance of each letter from the first letter, counted forward with wrap-around. Shifted keys have the same distances.
| i | key | Distances from the first letter | Groups after |
|---|---|---|---|
| 0 | abc | 0, 1, 2 | [0] |
| 1 | bcd | 0, 1, 2 | [0, 1] |
| 2 | az | 0, 25 | [0, 1], [2] |
| 3 | ba | 0, 25 | [0, 1], [2, 3] |
| 4 | xyz | 0, 1, 2 | [0, 1, 4], [2, 3] |
The groups are [[0, 1, 4], [2, 3]]. The key ba has the distance from b to a, counted forward, which is 25.
Input: keys = ["a", "z"]
Output: [[0, 1]]The keys a and z are shifts of each other, since a plus 25 is z. They share one group.
Input: keys = ["ab", "ac"]
Output: [[0], [1]]The keys ab and ac have different distances, 1 and 2, so each is alone.
0 ≤ keys.length ≤ 100,000 (stored keys)1 ≤ keys[i].length ≤ 20a to z.Comparing every pair of keys, and trying every shift, costs about n × n × 26 steps, far over budget. One canonical key per string costs L steps, so the whole job costs about n × 20 = 2 × 10^6. The map joins equal canonical keys.
group_shifted · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.