Group Shifted Strings

80.Group Shifted Strings

Hash Table

String

Problem Statement:

Given a list of strings, group all strings that belong to the same shifting sequence. A string's shifting sequence is defined as the difference in positions between consecutive characters in the string, considering alphabetical wrapping from 'z' to 'a'.

Algorithm:

1. Use a HashMap to group strings by their shift patterns.
2. For each string in the input:
• Calculate a unique key based on the differences between consecutive characters, adjusting for alphabetical wrapping.
• Append the computed differences to a StringBuilder, separated by delimiters to avoid collisions between keys.
• Insert the string into the map under the computed key.
3. Return the grouped strings as a list of lists, extracting the values from the map.

Complexity:

Time: O(n * m), where n is the number of strings and m is the average length of each string | Space: O(n * m)

Java Implementation:

public List> groupStrings(String[] strings) {
    // Map to store pattern key -> grouped strings
    Map> map = new HashMap<>();
    
    for (String str : strings) {
        // Build a key based on the shifts between consecutive characters
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length() - 1; i++) {
            // Calculate the difference between current and next character
            int diff = str.charAt(i + 1) - str.charAt(i);
            if (diff < 0) 
                diff += 26; // Wrap around to handle shifts like 'z' to 'a'
            
            // Append the difference and a delimiter to avoid collisions
            sb.append(diff).append(",");
        }
        
        // Use the computed key to group strings
        String key = sb.toString();
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(str);
    }
    
    // Return all grouped strings as a list of lists
    return new ArrayList<>(map.values());
}