Anagram Buckets


  • 3
    D

    Give a list of words like [rats, star, arts, cie, ice], group same anagrams into buckets and output them.
    [rats, star, arts]
    [cie, ice]


  • 6

    Group Anagrams

    A simple solution is go through the words list, for each word, sort its characters and form a map key, then add the word to the key, in the end, go through the hash map and print out the values (which are lists of grouped anagrams).


  • 0
    J

    @jeantimex

    what if the map keys for different anagrams are the same?


  • 0

    @Jeff-Jing
    Do you have an example of the input?


  • 0
    J

    @jeantimex yours works fine. I messed up hash code with may keys because I tried to find a solution without sorting string chars.


  • 2
    A
    typedef unordered_map<string, vector<string>> dict_bucket;
    dict_bucket anagram_classify(const vector<string>& v) {
      unordered_map<string, vector<string>> bucket;
      for(const string& s: v) {
        // (*) Get anagram of the word (*)
        vector<int> cnt(26, 0);
        for(char c: s) {
          cnt[c-'a']++;
        }
        std::string ana;
        for(int i = 0 ; i < 26 ; i++) {
          if (cnt[i] > 0) {
            ana += string(cnt[i], i+'a');
          }
        }
        // Store the string to the bucket
        bucket[ana].push_back(s);
      }
      return bucket;
    }
    

    You can replace (*) with sorting, but it's slightly less efficient in terms of time complexity, but better in space complexity.

    typedef unordered_map<string, vector<string>> dict_bucket;
    dict_bucket anagram_classify(const vector<string>& v) {
      unordered_map<string, vector<string>> bucket;
      for(string s: v) {
        sort(s.begin(), s.end());
        bucket[s].push_back(s);
      }
      return bucket;
    }
    

Log in to reply
 

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