Trie Solution O(N*M*logM) time, O(N*M) space (more space efficient than hashtable)


  • 2
    H

    Using Trie data structure:

    • O(NMlogM) time

    • O(N*M) space, but typically more space efficient when there are many strings with overlapping prefixes (after being sorted)

      class Node {
      private:
      int idx;
      vector<Node*> child;
      public:
      Node() {
      idx = -1;
      for (int i = 0; i < 26; i++) {
      child.push_back(NULL);
      }
      }
      ~Node() {
      for (int i = 0; i < 26; i++) {
      delete child[i];
      }
      }
      void createChild(int id) {
      child[id] = new Node();
      }
      Node* getChild(int id) {
      return child[id];
      }
      int getIdx() {
      return idx;
      }
      void setIdx(int newIdx) {
      idx = newIdx;
      }
      };

      class Trie {
      private:
      Node* _root;
      int cnt;
      public:
      Trie() {
      cnt = 0;
      _root = new Node();
      }
      ~Trie() {
      delete _root;
      }
      int insert(string &str) {
      int len = str.length();
      Node* curr = _root;
      for (int i = 0; i < len; i++) {
      if (curr->getChild(str[i] - 'a') == NULL) {
      curr->createChild(str[i] - 'a');
      }
      curr = curr->getChild(str[i] - 'a');
      if (i == len - 1) {
      if (curr->getIdx() == -1)
      curr->setIdx(cnt++);
      return curr->getIdx();
      }
      }
      if (len == 0) {
      if (_root->getIdx() == -1)
      _root->setIdx(cnt++);
      return _root->getIdx();
      }
      }
      };

      class Solution {
      vector<string> ans;
      vector<pair<int, int> > pairs;
      public:
      vector<string> anagrams(vector<string> &strs) {
      Trie *trie = new Trie();
      int cnt[strs.size()];
      memset(cnt, 0, sizeof(cnt));
      for (int i = 0; i < strs.size(); i++) {
      string sorted_strs = strs[i];
      sort(sorted_strs.begin(), sorted_strs.end());
      int idx = trie->insert(sorted_strs);
      pairs.push_back({i, idx});
      cnt[idx]++;
      }
      sort(pairs.begin(), pairs.end(), [](pair<int, int> a, pair<int, int> b){
      return a.second < b.second;
      });
      for (int i = 0; i < strs.size(); i++) {
      if (cnt[pairs[i].second] <= 1) continue;
      ans.push_back(strs[pairs[i].first]);
      }
      delete trie;
      return ans;
      }
      };


  • 0
    J

    Good practice for large input. (Obviously the OJ just use small inputs for every test case.) I must find a dictionary to try it.


Log in to reply
 

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