C++: Convert Jumple Word to Possible Words

[zizz]

If the input word / string is LARBITNLI, then the output should be TILL, TRILL and BRILLIANT.

I assume TILL, TRILL and BRILLIANT are in the dictionary and they're selected because they can be composed from the letters of LARBITNLI. Lets call this property composability.

It's especially easy to check for composability when both strings are sorted. Then it can be done in O(N), where N is the number of letters in the input string. And from this follows that its advantagous to have a version of the dictionary where each words string is presorted in letter order.

So checking for composability is O(N) but since N is limited (to 9) this operation finishes in constant time that is O(1).

What remains is a sequential scan where each of the presorted word strings in the dictionary is compared for composability with the sorted input string. And that's an O(N) operation where N is the number of words.

It's possible to refine this further by also keeping the dictionary of presorted word strings sorted. Then the input string can be checked for composability with the dictionary as a whole in a binary search fashion. This reduces complexity to O(logN).