fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <unordered_set>
  5. #include <unordered_map>
  6. #include <stdexcept>
  7. using namespace std;
  8.  
  9. class WordFinder {
  10. public:
  11.     struct Node {
  12.         char c;
  13.         unordered_map<char, Node*> children;
  14.         bool end = false;
  15.  
  16.         Node() : c(0), end(false) {}
  17.         Node(char ch) : c(ch), end(false) {}
  18.  
  19.         // In a complete solution, you'd want to add a destructor to free children.
  20.         ~Node() {
  21.             for (auto &entry : children) {
  22.                 delete entry.second;
  23.             }
  24.         }
  25.     };
  26.  
  27.     Node* root;
  28.     vector<char> charC;
  29.  
  30.     // Constructor: builds the trie from a list of words and copies the search characters.
  31.     WordFinder(vector<string>& words, vector<char>& c) {
  32.         root = new Node();
  33.         charC = c;
  34.         for (const string &w : words) {
  35.             insert(w);
  36.         }
  37.     }
  38.  
  39.     // Destructor to free allocated memory.
  40.     ~WordFinder() {
  41.         delete root;
  42.     }
  43.  
  44.     /** Inserts a word into the trie. */
  45.     void insert(const string &word) {
  46.         Node* temp = root;
  47.         for (char a : word) {
  48.             // Use unordered_map to check for the child.
  49.             if (temp->children.find(a) == temp->children.end()) {
  50.                 temp->children[a] = new Node(a);
  51.             }
  52.             temp = temp->children[a];
  53.         }
  54.         temp->end = true;
  55.     }
  56.  
  57.     // Recursive helper function to find words given available characters.
  58.     void find_r(vector<char>& chars, Node* cn, string curr_word, unordered_set<string>& res) {
  59.         if (cn == nullptr) return;
  60.         if (cn->end) {
  61.             res.insert(curr_word);
  62.         }
  63.         for (size_t i = 0; i < chars.size(); i++) {
  64.             if (chars[i] == '*') continue;
  65.             char temp = chars[i];
  66.             // Mark the character as used.
  67.             chars[i] = '*';
  68.             // Only proceed if there is a valid child.
  69.             if (cn->children.find(temp) != cn->children.end()) {
  70.                 find_r(chars, cn->children[temp], curr_word + temp, res);
  71.             }
  72.             // Restore the character.
  73.             chars[i] = temp;
  74.         }
  75.     }
  76.  
  77.     // Public function to initiate the word finding process.
  78.     unordered_set<string> find() {
  79.         unordered_set<string> res;
  80.         find_r(charC, root, "", res);
  81.         return res;
  82.     }
  83. };
  84.  
  85. int main() {
  86.     vector<string> words = {"word", "words", "wood", "order"};
  87.     vector<char> c = {'o','r','s','d','o','w','e'};
  88.     WordFinder wf(words, c);
  89.     unordered_set<string> res = wf.find();
  90.     for (const auto& r : res) {
  91.         cout << r << endl;
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
wood
word
words
https://ideone.com/yigjeV
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!