Practice/Meta/Leetcode 249. Group Shifted Strings

Leetcode 249. Group Shifted Strings

CodingMust

Problem

Given an array of strings, group together all strings that are equivalent under alphabetical shifting. Two strings belong to the same shift group if you can transform one into the other by shifting every character by the same amount in the alphabet, with wraparound from 'z' to 'a'.

For example, "abc" can be shifted to "bcd" by shifting each character forward by 1 position. Similarly, "xyz" can be shifted to "yza" by the same +1 shift pattern.

Return the grouped strings in any order. Within each group, the strings can appear in any order.

Requirements

1. Group strings based on their shift equivalence
2. A shift is valid only if all characters in a string are shifted by the same amount
3. Shifts must wrap around (after 'z' comes 'a')
4. Strings of different lengths cannot belong to the same shift group
5. Return groups as a list of lists

Constraints

• 1 ≤ strings.length ≤ 200
• 1 ≤ strings[i].length ≤ 50
• strings[i] consists of lowercase English letters only
• Expected time complexity: O(n * m) where n is the number of strings and m is the average string length
• Expected space complexity: O(n * m)

Examples

Example 1:

` Input: strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"] Output: [["abc","bcd","xyz"],["acef"],["az","ba"],["a","z"]] Explanation:

• "abc", "bcd", "xyz" all have the pattern (0,1,2) - each character is 1 more than the previous
• "acef" has pattern (0,2,3,4)
• "az" and "ba" both have pattern (0,25) - representing a wraparound shift
• "a" and "z" are single characters, all belonging to one group `

Example 2:

Input: strings = ["abc", "def", "ghi"] Output: [["abc","def","ghi"]] Explanation: All three strings have the same shift pattern (0,1,2)

Example 3:

Input: strings = ["a"] Output: [["a"]] Explanation: Single string forms its own group