Group Shifted Strings - Leetcode Solution

Group Shifted Strings is a problem on LeetCode that involves grouping a given set of strings together based on the shifts made to each of them. The problem statement is as follows:

Given a string, we can shift each of its characters to the right by one, and the last character becomes the first character. We can do this as many times as we want. For example, "abc" can be shifted to be "bcd", "cde", etc.

Given a list of strings, group all strings that belong to the same shifting sequence. You may assume that each string consists of lowercase alphabets only.

To solve this problem, we can start by observing that each string belongs to a unique shifting sequence. This is because any two strings that belong to the same shifting sequence must have the same relative distances between their characters. For example, if "abc" can be shifted to be "bcd", "cde", etc., then any string that can be shifted to be "abc" must have the same relative distances between its characters. This means that we can represent each shifting sequence by the distances between the characters in the first string of the sequence.

We can start by iterating through each string in the list and computing the distances between its characters. We can then use a dictionary to store the shifting sequences that we have seen so far. The keys of the dictionary will be the distances between the characters, and the values will be lists of strings that belong to that shifting sequence.

Here is the detailed solution:

1. Initialize an empty dictionary to store the shifting sequences.
2. Iterate through each string in the list: a. Compute the distances between the characters in the string by subtracting each character from the next character and taking the modulo 26. b. If the computed distances are negative, add 26 to them to get the correct distances. c. If the computed distances are not in the dictionary, add them as a new key with a value of an empty list. d. Append the current string to the list of strings corresponding to the computed distances.
3. Return the values of the dictionary, which will be lists of strings that belong to the same shifting sequence.

Here is the Python code implementation:

def groupStrings(strings: List[str]) -> List[List[str]]:
    sequences = {}
    for s in strings:
        distances = [(ord(s[i+1])-ord(s[i]))%26 for i in range(len(s)-1)]
        if -1 in distances:
            distances = [(d+26)%26 for d in distances]
        if tuple(distances) not in sequences:
            sequences[tuple(distances)] = []
        sequences[tuple(distances)].append(s)
    return list(sequences.values())

In this implementation, we are using a tuple of distances as the key for the dictionary, since dictionaries cannot have lists as keys. We are also taking the modulo 26 of the distances to handle cases where the characters "wrap around" from 'z' to 'a'.

1