Group Shifted Strings Python Solution

LeetCode 249, Medium. Topics: Array, Hash Table, String. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 249   # by problem number
lcpy gen -s group_shifted_strings   # by problem name

Problem

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.

Examples

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

Input: strings = ["a"]
Output: [["a"]]

Constraints

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

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import defaultdict


class Solution:
    # Time: O(L) where L is total length of all strings
    # Space: O(L)
    def group_strings(self, strings: list[str]) -> list[list[str]]:
        groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)
        for s in strings:
            shift = ord(s[0]) - ord("a")
            key = tuple((ord(c) - ord("a") - shift) % 26 for c in s)
            groups[key].append(s)
        return list(groups.values())

Complexity

Time	Space
O(L) where L is total length of all strings	O(L)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Group Shifted Strings Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags