[Problem 131] Four Pics One Word
Back to Problem Solutions forum
I was looking for any hint on an algorithm I might not know about. A brute force approach of this problem is clearly untenable.
For example one of the lines in the problem data set was 10 <16 letters>. This leaves us with 8008 unique subsets of those letters(C(16,10)). But each of those subsets could be rearanged 10! ways wich leaves a total of just over 29 billions potential words to check.
I'm clearly missing some optimization if anyone has a hint of where to look.
Hi Tony,
Maybe you're overthinking this one a bit!
For each test case, look through the dictionary for words of the correct length. For each word of the correct length, can it be made from the given set of letters?
Ah yes, I'm silly. I was doing the problem backwards :) I had made such a good algorithm for finding the next lexicographcic subset of length X for a given set :)