group_shifted_strings

View Source

 1from collections import defaultdict
 2
 3
 4# @leet start
 5class ShiftedString:
 6    def __init__(self, s) -> None:
 7        self.s = s
 8
 9    def __hash__(self) -> int:
10        key = []
11        for l, r in zip(self.s, self.s[1:]):
12            key.append((ord(r) - ord(l)) % 26 + ord("a"))
13        return hash(tuple(key))
14
15
16class Solution:
17    def groupStrings(self, strings: list[str]) -> list[list[str]]:
18        """
19        This question asks us to group all strings that can either be right or
20        left shifted with each other. For example, 'az' can be shifted into 'ba'
21        by doing one right shift, which wraps around.
22
23        To do this, we encode the rules into a hashmap and then return all the
24        strings that hash to the same value.
25
26        The hash consists of the amount of shifts from the previous character it
27        is. We can zip and iterate through the string to find this out.
28        """
29        groups = defaultdict(list)
30        for string in strings:
31            groups[hash(ShiftedString(string))].append(string)
32
33        return list(groups.values())
34
35
36# @leet end
37
38
39def test():
40    assert 2 + 2 == 4

class ShiftedString: View Source

 6class ShiftedString:
 7    def __init__(self, s) -> None:
 8        self.s = s
 9
10    def __hash__(self) -> int:
11        key = []
12        for l, r in zip(self.s, self.s[1:]):
13            key.append((ord(r) - ord(l)) % 26 + ord("a"))
14        return hash(tuple(key))

ShiftedString(s) View Source

7    def __init__(self, s) -> None:
8        self.s = s

class Solution: View Source

17class Solution:
18    def groupStrings(self, strings: list[str]) -> list[list[str]]:
19        """
20        This question asks us to group all strings that can either be right or
21        left shifted with each other. For example, 'az' can be shifted into 'ba'
22        by doing one right shift, which wraps around.
23
24        To do this, we encode the rules into a hashmap and then return all the
25        strings that hash to the same value.
26
27        The hash consists of the amount of shifts from the previous character it
28        is. We can zip and iterate through the string to find this out.
29        """
30        groups = defaultdict(list)
31        for string in strings:
32            groups[hash(ShiftedString(string))].append(string)
33
34        return list(groups.values())

def groupStrings(self, strings: list[str]) -> list[list[str]]: View Source

18    def groupStrings(self, strings: list[str]) -> list[list[str]]:
19        """
20        This question asks us to group all strings that can either be right or
21        left shifted with each other. For example, 'az' can be shifted into 'ba'
22        by doing one right shift, which wraps around.
23
24        To do this, we encode the rules into a hashmap and then return all the
25        strings that hash to the same value.
26
27        The hash consists of the amount of shifts from the previous character it
28        is. We can zip and iterate through the string to find this out.
29        """
30        groups = defaultdict(list)
31        for string in strings:
32            groups[hash(ShiftedString(string))].append(string)
33
34        return list(groups.values())

This question asks us to group all strings that can either be right or left shifted with each other. For example, 'az' can be shifted into 'ba' by doing one right shift, which wraps around.

To do this, we encode the rules into a hashmap and then return all the strings that hash to the same value.

The hash consists of the amount of shifts from the previous character it is. We can zip and iterate through the string to find this out.

def test(): View Source

40def test():
41    assert 2 + 2 == 4