1

I'm writing a program that can take a string input and find all the possible dictionary words that can be made from the letters in the input. My current solution is:

    for i in range(len(userInput) + 1):
        permutations = list(itertools.permutations(userInput, i))
        for letter in permutations:
            joinedPermutations = ''.join(letter)
            if joinedPermutations not in wordCombinations and len(joinedPermutations) > 1: # wordCombinations stores all the matching words.
                for lines in fetchedFiles: # fetchedFiles is a list of all the dictionary words of a given letter.
                        if joinedPermutations in lines:
                            wordCombinations.append(joinedPermutations)

This method works well for small inputs however, once larger inputs are used, it can take hundreds of thousands of passes to find all the permutations. I do understand using permutations isn't the most efficient method of finding combinations, but I lack the knowledge to make it more efficient.

What would be a more efficient method of finding dictionary words from an input string?

I don't necessarily need to use this method I've created, it is just the only one I thought of.

funnydman
  • 9,083
  • 4
  • 40
  • 55
jdow
  • 11
  • 2
  • This question basically answers what you are looking for, efficient ways to calculate all the permutations of a string, [Generate list of all possible permutations of a string](https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string) – ErrorEliminator Aug 20 '22 at 16:33
  • 2
    You could maybe first read in dictionary of words and break it up into different buckets depending on the length and characters included. – GordonAitchJay Aug 20 '22 at 16:37
  • 2
    Create a dictionary mapping from the sorted letters of the word to the words with those letters. So you'll have things like, `..., 'aegln': ['angel', 'glean'], ...` in it. And now given an input like `algaen` you can sort its letters, look in the dictionary, and give the answer instantly. Search for "anagram" to find more. – btilly Aug 20 '22 at 17:40
  • Does this answer your question? [Generate list of all possible permutations of a string](https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string) – S H Aug 20 '22 at 20:14

0 Answers0