C++ O(n) runtime complexity 60ms


  • 0
    Z
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> v;
        if(!strs.size()) return v;
        unordered_map<string, int> m;
        for(string &s : strs){
            string tmp(s);
            sort(tmp.begin(), tmp.end());
            auto f = m.find(tmp);
            if(f != m.end()){
                v[f->second].push_back(s);
                sort(v[f->second].begin(), v[f->second].end());
            }
            else{
                v.push_back(vector<string>({s}));
                m[tmp] = v.size() - 1;
            }
        }
        return v;
    }

  • 0
    E

    is this O(1) space? You have a hittable that has O(n) elements, no?


  • 0
    Z

    Yes, you are right. I don't remember why I thought it is O(1) space since size of the map is unknown but thanks for letting me know.


  • 0
    G

    how could it be O(N) since you are using sort and map in the loop. You can't ignore them.


  • 0
    Z

    I think N is the number of string rather than char


  • 0
    Y

    It is O(nlogn) because of sort.


Log in to reply
 

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