How to get all dictionary words from a list of letters?

Question

I have an input string, like "fairy", and I need to get the English words that can be formed from it. Here's an example:

5: Fairy
4: Fray, Airy, Fair, Fiar
3: Fay, fry, arf, ary, far, etc.

I have an std::unordered_set<std::string> of dictionary words so I can easily iterate over it. I've created permutations before as shown below:

std::unordered_set<std::string> permutations;

// Finds every permutation (non-duplicate arrangement of letters)
std::sort(letters.begin(), letters.end());
do {
    // Check if the word is a valid dictionary word first
    permutations.insert(letters);
} while (std::next_permutation(letters.begin(), letters.end()));

That's perfect for length 5. I can check each letters to see if it matches and I end up with "fairy", which is the only 5 letter word that can be found from those letters.

How could I find words of a smaller length? I'm guessing it has to do with permutations as well, but I wasn't sure how to implement it.

Answer 1

You can keep an auxiliary data structure and add a special symbol to mark an end-of-line:

#include <algorithm>
#include <string>
#include <set>
#include <list>
#include <iostream>
 
int main()
{
    std::list<int> l = {-1, 0 ,1, 2, 3, 4};
    std::string s = "fairy";
    std::set<std::string> words;
    do {
        std::string temp = "";
        for (auto e : l)
            if (e != -1) temp += s[e];
            else break;
        words.insert(temp);
    } while(std::next_permutation(l.begin(), l.end()));
}

Here the special symbol is -1