How to build a dictionary in such a way that it'd be efficient to search for all valid words which are permutations of a given string?

For each word in a dictionary as a value, build a key which is composed of lexicographically ordered characters. For example, value = apple key = aelpp. value = ocotopus key = cooopstu Then build an index from the keys, and you'll have all of the words that can be generated from re-ordering the elements. The result is efficient at run-time because it's constant run time. The construction of the index is also efficient because it only needs to run linearly, once.

Perhaps use a function of the sum of the string's char codes (and its length?) as a key in a first hashtable. This key should link to a second hashtable that would directly index each particular permutation of the word.

Hash table