C++ Solution


  • 2
    A

    Approach #1 (Brute Force) [Time Limit Exceed]

    Explanation
    Simple brute force method is to traverse the input string and compare it with other string to check whether they are anagram or not.
    If two string are anagram then there alphabetically sorted form are equal.

    Algorithm.
    We maintain an array vis[] to check that string is included in anagram or not. We traverse input array , if we found a string with vis[i]=false then sort the string in an alphabetical order and store this sorted string in a key variable.Then traverse remaining input aray and compare each string (in sorted form) with a key, if it is equal to the key , then push it to a vector and update vis[j] array to true.

    C++

    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            vector<vector<string>> ans;
            int n=strs.size();
            if(n<1)
            {
                return ans;
            }
            bool vis[n]={false};
            for(int i=0;i<n;i++)
            {
                if(!vis[i])
                {
                    vector<string> s;
                    string key=strs[i];
                    sort(key.begin(),key.end());
                    s.push_back(strs[i]);
                    vis[i]=true;
                    for(int j=i+1;j<n;j++)
                    {
                        if(!vis[j])
                        {
                            string check=strs[j];
                            sort(check.begin(),check.end());
                            if(!key.compare(check))
                            {
                                s.push_back(strs[j]);
                                vis[j]=true;
                            }
                        }
                    }
                    ans.push_back(s);
                }
            }
            return ans;
        }
    };
    

    Approach #2 [Accepted]

    Explanation
    The idea is to use a map to store those strings that are anagrams. We use the alphabetically sorted string as the key and the vector of anagram string as the value.
    We can notice that if two string are anagram then there alphabetically sorted form are equal. For example- take two anagram string "tea" and "eat", there sorted form are "aet" and "aet" which are equal. So we can use this properties to use sorted string as key value and vector of anagram as a map value.

    Algorithm.
    Traverse the input array and sort the string in an alphabetical order. Use this sorted string as a key. If this key is not present in map then insert key to the map otherwise update the key value.

    Finally push all map value to a vector.

    C++

    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            map <string,vector<string>> m;
            for(int i=0;i<strs.size();i++)
            {
                string key=strs[i];
                sort(key.begin(),key.end());
                if(m.find(key)==m.end())
                {
                    vector<string> v;
                    v.push_back(strs[i]);
                    m[key]=v;
                }
                else
                {
                    m[key].push_back(strs[i]);
                }
            }
            vector<vector<string>> ans;
            map <string,vector<string>> :: iterator it;
            for(it=m.begin();it!=m.end();it++)
            {
                ans.push_back(it->second);
            }
            return ans;
        }
    };
    

    Approach #3 [Accepted]

    Explanation
    In this approach algorithm is same as approach 2, but we can speed up our program by change in sorting process. generally sort function takes O(nlogn) time , but here string contains only lower-case alphabets. so we can write a count sort function (O(n) time) to speed up our program.

    C++

    class Solution {
    public:
        string count_sort(string s)
        {
            int count[26] = {0};
            int n = s.length();
            for(int i=0;i<n;i++)
            {
                count[s[i]-'a']++;
            }
            string ans;
            int p = 0;
            for(int i=0;i<26;i++)
            {
                for(int j=0;j<count[i];j++)
                {
                    ans+=(char)('a'+i);
                }
            }
            return ans;
        }
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            map <string,vector<string>> m;
            for(int i=0;i<strs.size();i++)
            {
                string key=strs[i];
                key=count_sort(key);
                cout<<key<<" ";
                if(m.find(key)==m.end())
                {
                    vector<string> v;
                    v.push_back(strs[i]);
                    m[key]=v;
                }
                else
                {
                    m[key].push_back(strs[i]);
                }
            }
            vector<vector<string>> ans;
            map <string,vector<string>> :: iterator it;
            for(it=m.begin();it!=m.end();it++)
            {
                ans.push_back(it->second);
            }
            return ans;
        }
    };
    

  • 0
    C
    This post is deleted!

  • 0
    A

    Can you tell which part I copied from you??


  • 0
    C

    @ayush_swm-0
    In your "Time complexity analysis", you have

    Time Complexity = O(n*klogk), where n is the number of strings, and k is the maximum length of the strings.

    We loop through the input array which takes O(n) time , for each iteration we use sort function which takes O(klogk)
    time assuming k as a length of string. So total time is O(n*klogk).

    Space complexity : O(n * k).

    That was edited after I published my content

    Time complexity : $$O(n* klogk)$$ where n is the number of strings in the input, and k is the max length of the strings.

    We loop through the input array which take $$O(n)$$ time, for each iteration of the loop, we sort the string, assuming the string length is k, a regular sorting algorithm takes $$O(klogk)$$ time to sort. So the total time for the loop is $$O(n * klogk)$$.

    At the end we use $$O(n)$$ time to convert the dictionary to list.

    So the total time for the algorithm is $$O(n * klogk) + O(n) = O(n * klogk)$$.

    Space complexity : $$O(n * k)$$. We create a dictionary to store all the strings which takes $$O(n * k)$$ space.

    Anyway, I will try to report this since plagiarism is really a big shame in publishing content.


  • 0
    A

    First notice one thing all content of this article is not written at same time. I had edited this article several time. First I had written only one accepted solution , then after I addded brute force solution , after this I added detailed explanation of solution , and at last added time complexity analysis.
    As you mention I had copied only your time complexity part, please note that if I can write code by my own then I can also find time complexity by my own (you know it's not a complex code to find time coplexity).


  • 0
    C

    @ayush_swm-0 thanks for admitting that you did plagiarize my content. I didn't read your article carefully so I don't know if any other parts are also plagiarized from my content, if LeetCode had your edit history, it should be easy for them to find out.
    It doesn't matter if it's easy or hard to come up with an idea and write it out, Plagiarism is Plagiarism, please find out what Plagiarism means here(Wikipedia link) if you don't understand it.
    Anyway, I will let the leetcode moderator decide.


  • 0
    A

    Then go on who's stopping you , read my whole article carefully.

    First tell me how you conclude that I admit for copying your content.
    Read again my reply carefully.

    As you mention I had copied only your time complexity part, please note that if I can write code by my own then I can also find time complexity by my own (you know it's not a complex code to find time coplexity).

    Here I am not admitting anything , I am simply explaining that I written complexity analysis by my own.

    And yes it's a strong favour for me that Leetcode moderator can see my edit history and also all my right solution to this problem that I submitted earlier.


  • 1
    C

    @ayush_swm-0

    please note that if I can write code by my own then I can also find time complexity by my own

    Haha this is the first time I've ever heard this. There are plenty of people in the world(might include you) who can write code but have no idea about time complexity.
    Also many dishonest people :)
    Wish you luck.


  • 0
    A

    Well I don't want to jump into fight with you.

    I will mail Leetcode moderator and explain him detailed situation.

    Till then I am removing complexity part (now again not assume that I am admitting for copying your content).

    Let moderaror to decide.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.