SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The core idea is to group strings that are anagrams of each other. Anagrams, when sorted, result in the same string. By using this property, we can group all anagrams together.

Approach

1. Initialize a Dictionary:

   Create an empty dictionary to store groups of anagrams.

2. Iterate Through Each String:

   For each string in the input list:

   • Sort the string to obtain a common representation for all its anagrams.

   • Use the sorted string as the key and append the original string to the list of values for that key in the dictionary.

3. Collect Results:

   After processing all strings, the values of the dictionary will be the required groups of anagrams.

4. Return the Result:

   Convert the values of the dictionary to a list and return it.

Complexity

Time Complexity:

O(n * k log k), where n is the number of strings and k is the maximum length of a string. Sorting each string takes O(k log k) time and we do this for each string.

Space Complexity:

O(n * k), where n is the number of strings and k is the maximum length of a string. In the worst case, all strings are different and we store each string in the dictionary.

Code

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> myMap;
        for (auto& ele : strs) {
            string eleSorted = ele;
            sort(eleSorted.begin(), eleSorted.end());
            myMap[eleSorted].push_back(ele);
        }
        vector<vector<string>> result;
        for (auto& pair : myMap) {
            result.push_back(pair.second);
        }
        return result;
    }
};

Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}
        for s in strs:
            # Sort the string and use it as a key
            sorted_str = ''.join(sorted(s))
            if sorted_str not in anagrams:
                anagrams[sorted_str] = []
            anagrams[sorted_str].append(s)
        return list(anagrams.values())

Java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> myMap = new HashMap<>();
        for (String ele : strs) {
            char[] charArray = ele.toCharArray();
            Arrays.sort(charArray);
            String eleSorted = new String(charArray);
            if (!myMap.containsKey(eleSorted)) {
                myMap.put(eleSorted, new ArrayList<>());
            }
            myMap.get(eleSorted).add(ele);
        }
        return new ArrayList<>(myMap.values());
    }
}

JavaScript

var groupAnagrams = function (strs)
{
    let myMap = new Map();
    strs.forEach((ele) =>
    {
        let eleSorted = ele.split('').sort().join('');
        if (myMap.has(eleSorted)) 
        {
            myMap.set(eleSorted, [ele, ...myMap.get(eleSorted)])
        }
        else
            myMap.set(eleSorted, [ele])
    })
    return (Array.from(myMap.values()))

};