I'm fairly new to C++, and as an exercise, I'm trying to write a "word unscrambler". That is, I have a large text file full of words that is loaded into a trie. Each trie_node has an array of 27 trie_nodes which are by default NULL unless that element shares the same position as a letter in the alphabet that can follow the letter the trie_node represents. The 27 element indicates that the word can end at that node.
I have this class that I want to permute through all letter combinations, but doesn't bother going through letter combinations that are impossible.
What I've written almost has what I need. However, it only works with very specific combinations of letters.
For instance, if you input the letters "last" you get the following words:
last salt slat However, if you input the word "salt" (a permutation of "last"), you only get this:
salt I'm pretty sure the problem is in my permute() method. What's the most efficient way to find these words without iterating through all permutations and comparing that to the word list (which would be an 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; for (pos2 = pos; pos2 < len; ++pos2) { char* j = word + pos2; const trie_node* _next = next(node, *j); if (_next) { // check if that's a valid path char* i = word + pos; swap(i, j); // swap letters permute(word, _next, pos, len); // find that route swap(i, j); // switch back } } } } 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; for (map<string, short>::const_iterator it = _found.begin(), e = _found.end(); it != 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; for (size_t i = 0; i < 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 i = 0; for (; i < 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; } }; 2 Answers
IIUC you are trying to find all anagrams of a word in a dictionary. The best way to do this is as follows:
1. Create map from string to list of strings. 2. For each word in dictionary. a. Let sortedWord = sort letters in word lexicographically. b. Add word to the list in the map whose key is sortedWord 3. Let searchWord be the word whose anagrams you are looking for. 4. Let sortedSearchWord = sort letters in searchWord lexicographically. 5. Return map[sortedSearchWord] Assuming the longest word in the dictionary has k letters and there are n words, this algorithm runs in O(n*k*log(k)) to build the map and then it runs in O(k*log(k)) to find anagrams of a given words.
Thanks for your suggestions. I streamlined the whole thing with this:
#include <iostream> #include <string> #include <algorithm> #include <fstream> using namespace std; inline void sort(string& str) { sort(str.begin(), str.end()); } void findwords(string& letters, istream& in, ostream& out) { sort(letters); string word; while (getline(in, word)) { string token(word); sort(token); if (token == letters) { out << word << endl; } } } int main(int argc, char* argv[]) { if (argc != 2) { cout << "usage: scramble <word>" << endl; return 1; } ifstream wordsfile; wordsfile.open("words.txt"); if (!wordsfile.is_open()) { cout << "unable to load words.txt" << endl; return 2; } string words(argv[1]); findwords(words, wordsfile, cout); wordsfile.close(); return 0; } This pretty much solves everything. However, I may want to add functionality to find all possible words in a string, not just anagrams, but that's another project.
