Dant3
BAN USERJust a high level idea:
1. For each word in dictionary, generate all permutations. IMO this should take linear time wrt number of words as long as words have a small upper-bound on their length, say 10-12. Plus, we are doing this just once and then use it multiple times for unscrambling.
2. Build a suffix-tree on all the original words and their permutations.
3. For unscrambling, scan the input string and back track over all the matches found to find the exact match of the string. Finding all matches should not be difficult as we can consider all the suffixes in the input string and look for them into the big suffix-tree of words to find matches. Also note that all permutations of a word are assumed to have a pointer back to the original word.
Edit: Last stage actually does not need to perform a back track. Consider the chars of input string as nodes of a DAG starting from left to right. For each match found draw an edge from the beginning vertex to the ending vertex. Then, unscrambling is just finding a path from the left-most node to right-most node.
The complexity of building the suffix-tree is O(L_dic) where L_dic is the sum of the length of all words in dictionary. The complexity of unscrambling the string S is O(|S|) since that is the upper bound on the number of edges we form in the end. Considering that we do unscrambling repetitively, building of suffix-tree should not be an issue.
Build a suffix array on the dictionary entries.
- Dant3 October 29, 2016Insert all the suffixes of the input string into the array and look at longest common prefixes they make with suffix array entries.
Complexity is linear in total length of dictionary entries.