LeetCode 249: Group Shifted Strings Solution

Master LeetCode problem 249 (Group Shifted Strings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

249. Group Shifted Strings

Medium

Array Hash Table String

Problem Explanation

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:

Initialize a hashmap to store the groups of shifted strings.
Iterate through each string in the input list.
For each string, calculate the key based on the relative shifts of characters.
Add the string to the corresponding group in the hashmap based on the key.
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. :

Solution Code

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();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 249 (Group Shifted Strings)?

This page provides optimized solutions for LeetCode problem 249 (Group Shifted Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 249 (Group Shifted Strings)?

The time complexity for LeetCode 249 (Group Shifted Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 249 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 249 in Java, C++, or Python.

Back to LeetCode Solutions