Word Unscrambler Difficulty Class
I am not that well versed in the area of complexity classes and related concepts. But will the problem tell if a given scrambled word is a real English word, a P or NP problem? (if it even makes sense) All programs I've seen take input and generate all permutations of a word, and then compare all permutations against every word in the dictionary. What if there was a different algorithm that took a different, more efficient approach? Will this change the complexity of the problem class? Sorry if I am using terminolgy wrong
source to share
Constructing word substitutions with k necessarily has exponential complexity, since there are k! permutations and the algorithm must create all of them. However, the search portion can be made more efficient by using a data structure called a hash table that allows searches to be performed at near constant times.
source to share
The number of English words is limited, and so it is obvious that the possible length of any English word is limited, so technically your problem is solvable in constant time (although the constant will be large). If you rephrase your question as you speak, you are presented with a dictionary of arbitrarily long alphabetically, and then for the query word you want to define the answer, then things get more interesting. Then the answer given by @fbg will probably be your best way; a hash of tuples of the number of occurrences of each letter (for example, taking the alphabet in some ordered order), for each word in your dictionary, and then if you are given a scrambled word and do the same hash, you can tell very quickly, your scrambled word query could be "unscrambled" to give a solution,otherwise, there is no solution in your dictionary.
source to share