permutation - C++ word unscrambler -
i'm new c++, , exercise, i'm trying write "word unscrambler". is, have large text file full of words loaded trie. each trie_node has array of 27 trie_nodes default null unless element shares same position letter in alphabet can follow letter trie_node represents. 27 element indicates word can end @ node.
i have class want permute through letter combinations, doesn't bother going through letter combinations impossible.
what i've written has need. however, works specific combinations of letters.
for instance, if input letters "last" following words:
last salt slat however, if input word "salt" (a permutation of "last"), this:
salt i'm pretty sure problem in permute() method. what's efficient way find these words without iterating through permutations , comparing word list (which expensive n! operation)?
#pragma once #include <map> #include <string> #include <fstream> #include "trie.h" using std::ifstream; using std::string; using std::map; class words { private: trie_node* wordend; // end marker trie_node wordbank; map<string, short> _found; template <typename e> static void swap(e* i, e* j) { e k = *i; *i = *j; *j = k; } void permute(char* word, const trie_node* node, size_t pos, size_t len) { if (is_word(word, len)) { string str_word(word, len); _found[str_word] = 0; } if (pos < len - 1) { size_t pos2; (pos2 = pos; pos2 < len; ++pos2) { char* j = word + pos2; const trie_node* _next = next(node, *j); if (_next) { // check if that's valid path char* = word + pos; swap(i, j); // swap letters permute(word, _next, pos, len); // find route swap(i, j); // switch } } } } public: words() : wordbank(27) { wordend = new trie_node(1); } words(const words& other) : wordbank(27) { operator=(other); } ~words() { delete wordend; } words& operator=(const words& other) { if (this != &other) { wordend = new trie_node(*wordend); wordbank = other.wordbank; _found = other._found; } return *this; } void clear() { _found.clear(); } void permute(char* word, size_t len) { permute(word, &wordbank, 0, len); } size_t size() const { return _found.size(); } size_t found(string buff[], size_t len) const { if (len > _found.size()) { len = _found.size(); } size_t index = 0; (map<string, short>::const_iterator = _found.begin(), e = _found.end(); != e; ++it) { buff[index] = it->first; if (++index == len) { break; } } return len; } const trie_node* next(char c) const { return next(&wordbank, c); } static const trie_node* next(const trie_node* n, char c) { if (isalpha(c)) { size_t pos = tolower(c) - 'a'; return n->operator[](pos); } return null; } bool is_word(const char* word, size_t len) const { const trie_node* node = &wordbank; (size_t = 0; < len; ++i) { if (isalpha(word[i])) { size_t index = tolower(word[i]) - 'a'; const trie_node* next = node->operator[](index); if (!next) { return false; } node = next; } } return node->operator[](26) == wordend; } bool load(const string& path) { ifstream wordfile; wordfile.open(path); if (!wordfile.is_open()) { return false; } trie_node* node = &wordbank; string word; while (getline(wordfile, word)) { size_t = 0; (; < word.size(); ++i) { size_t index = word[i] - 'a'; trie_node* _next = (*node)[index]; if (!_next) { _next = node->branch(index); } node = _next; if (i == word.size() - 1) { _next->set(26, wordend); } } } wordfile.close(); return true; } };
iiuc trying find anagrams of word in dictionary. best way follows:
1. create map string list of strings. 2. each word in dictionary. a. let sortedword = sort letters in word lexicographically. b. add word list in map key sortedword 3. let searchword word anagrams looking for. 4. let sortedsearchword = sort letters in searchword lexicographically. 5. return map[sortedsearchword] assuming longest word in dictionary has k letters , there n words, algorithm runs in o(n*k*log(k)) build map , runs in o(k*log(k)) find anagrams of given words.
Comments
Post a Comment