LeetCode 249: Group Shifted Strings

Explanation:

Given a list of strings, we need to group the strings that are shifted versions of each other together. Two strings are considered shifted if they have the same length and the difference between the ASCII values of corresponding characters is the same for all characters.

To solve this problem, we can use a hashmap to group the shifted strings. For each string, we calculate the key based on the relative shifts of characters and add the string to the corresponding group in the hashmap. Finally, we return all the grouped strings.

Algorithm:

1. Initialize a hashmap to store the groups of shifted strings.
2. Iterate through each string in the input list.
3. For each string, calculate the key based on the relative shifts of characters.
4. Add the string to the corresponding group in the hashmap based on the key.
5. Return the values of the hashmap as the result.

Time Complexity:

The time complexity of this algorithm is O(n * m), where n is the number of strings and m is the average length of the strings.

Space Complexity:

The space complexity is O(n * m) to store the hashmap. :

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strings) {
            String key = getKey(s);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
    
    private String getKey(String s) {
        StringBuilder key = new StringBuilder();
        for (int i = 1; i < s.length(); i++) {
            int diff = (s.charAt(i) - s.charAt(i - 1) + 26) % 26;
            key.append(diff).append(",");
        }
        return key.toString();
    }
}