SHARE
TWEET

Word Ladder II - Trie sem wildcard

a guest Mar 26th, 2020 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct TrieNode {
  2.   vector<int> end_words;
  3.   unordered_map<char, unique_ptr<TrieNode>> children;
  4. };
  5.  
  6. class Trie {
  7. public:
  8.   void insert(const string& word, int word_index) {
  9.     TrieNode* curr;
  10.     curr = &head;
  11.    
  12.     for (const char c : word) {
  13.       TrieNode* next;
  14.       auto it = curr->children.find(c);
  15.       if (it != curr->children.end()) {
  16.         next = it->second.get();
  17.       } else {
  18.         next = new TrieNode();
  19.         curr->children[c] = unique_ptr<TrieNode>(next);
  20.       }
  21.       curr = next;
  22.     }
  23.     curr->end_words.push_back(word_index);
  24.   }
  25.  
  26.   vector<int> findOneDiffs(const string& word, int word_index) {
  27.     vector<pair<TrieNode*, bool>> curr;
  28.     curr.push_back(make_pair(&head, false));
  29.    
  30.     for (const char c : word) {
  31.       vector<pair<TrieNode*, bool>> next_curr;
  32.       for (const auto& p : curr) {
  33.         TrieNode* node = p.first;
  34.         bool used_wildcard = p.second;
  35.         if (!used_wildcard) {
  36.           for (auto& child : node->children) {
  37.             next_curr.push_back(make_pair(child.second.get(), true));
  38.           }
  39.         }
  40.         auto it = node->children.find(c);
  41.         if (it != node->children.end()) {
  42.           next_curr.push_back(make_pair(it->second.get(), used_wildcard));
  43.         }
  44.       }
  45.       swap(curr, next_curr);
  46.     }
  47.    
  48.     vector<int> result;
  49.     for (const auto& p : curr) {
  50.       TrieNode* node = p.first;
  51.       for (const int i : node->end_words) {
  52.         if (i != word_index) {
  53.           result.push_back(i);
  54.         }
  55.       }
  56.     }
  57.     return result;
  58.   }
  59.  
  60. private:
  61.   TrieNode head;
  62. };
  63.  
  64. class Solution {
  65. public:
  66.  
  67.   vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
  68.     wordList.push_back(beginWord);
  69.     vector<vector<int>> transform (wordList.size());
  70.  
  71.     int target = -1;
  72.     for (int i = 0; i < wordList.size() - 1; i++) {
  73.       if (endWord == wordList[i]) {
  74.         target = i;
  75.         break;
  76.       }
  77.     }
  78.     if (target == -1) {
  79.       return vector<vector<string>>();
  80.     }
  81.  
  82.     Trie trie;
  83.     for (int i = 0; i < wordList.size(); i++) {
  84.       trie.insert(wordList[i], i);
  85.     }
  86.    
  87.     for (int i = 0; i < wordList.size(); i++) {
  88.       vector<int> one_diffs = trie.findOneDiffs(wordList[i], i);
  89.       for (const int j : one_diffs) {
  90.         transform[i].push_back(j);
  91.       }
  92.     }
  93.    
  94.     vector<vector<vector<string>>> ways_to_get(wordList.size());
  95.     deque<int> next;
  96.     vector<int> distance(wordList.size(), -1);
  97.    
  98.     next.push_back(wordList.size() - 1);
  99.     distance[wordList.size() - 1] = 0;
  100.     ways_to_get[wordList.size() - 1].push_back({wordList[wordList.size() - 1]});
  101.    
  102.     while (!next.empty()) {
  103.       int curr = next.front();
  104.       next.pop_front();
  105.       if (curr == target) {
  106.         break;
  107.       }
  108.      
  109.       for (const int i : transform[curr]) {
  110.         if (distance[i] == -1) {
  111.           distance[i] = distance[curr] + 1;
  112.           next.push_back(i);
  113.         }
  114.         if (distance[i] == distance[curr] + 1) {
  115.           for (vector<string> v : ways_to_get[curr]) {
  116.             v.push_back(wordList[i]);
  117.             ways_to_get[i].push_back(v);
  118.           }
  119.         }
  120.       }
  121.     }
  122.     return ways_to_get[target];
  123.   }
  124. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top