c++ 39ms sort version


  • 0
    S

    The general idea is:
    1 Sort chars in every string, so strings in the same group will be the same.
    2 Sort the sorted string, so strings in the same group will be together.
    3 Split the group.

       struct Node {
            string origin;
            string sorted;
            Node(string s) {
                origin = s;
                sorted = s;
                sort(sorted.begin(),sorted.end());
            }
            friend bool operator<(const Node& l, const Node& r) {
                return l.sorted < r.sorted;
            }
        };
        
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            vector<Node> v;
            for(string& s:strs) {
                v.push_back(Node(s));
            }
            sort(v.begin(),v.end());
            vector<vector<string>> ret;
            int index=0;
            vector<string> curr;
            while(index<v.size()) {
                curr.push_back(v[index].origin);
                ++index;
                if(index==v.size()) break;
                if(v[index].sorted != v[index-1].sorted) {
                    ret.push_back(curr);
                    curr.clear();
                }
            }
            if(curr.size()>0) {
                ret.push_back(curr);
            }
            return ret;
        }
    

Log in to reply
 

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