Valid Permutations of a String

Question

This question was asked to me in a recent amazon technical interview. It goes as follows:-

Given a string ex: "where am i" and a dictionary of valid words, you have to list all valid distinct permutations of the string. A valid string comprises of words which exists in the dictionary. For ex: "we are him","whim aree" are valid strings considering the words(whim, aree) are part of the dictionary. Also the condition is that a mere rearrangement of words is not a valid string, i.e "i am where" is not a valid combination.

The task is to find all possible such strings in the optimum way.

Did you attempt to answer this interview question, and, if so, can you share any code already have? — Tim Biegeleisen, Dec 18 '16 at 05:38
@TimBiegeleisen i thought of generating the various permutations of the string and den checking if each permutation can be broken down into valid words using dynamic programming. — Vaibhav Arora, Dec 18 '16 at 05:48
@Tony space does not count, the valid strings may have any number of spaces — Vaibhav Arora, Dec 18 '16 at 12:00
Considering the permutation of the string is not "optimal" because of the exponential growth of the factorial. Instead I would suggest selecting the words in the dictionary whose characters are among the non-blank characters of the string. In one pass you will substantially reduce the size of the dictionary. Then, consider one of these words at a time. For every word remove its characters from the string and repeat the former selection for the shortened string, etc. — Leandro Caniglia, Dec 18 '16 at 20:28
Consider arranging your dictionary as a *trie*. Add imaginary pointers from the end of each word back to the root of the dictionary. Then the task of selecting word sequences reduces to finding all different cyclic paths in the dictionary graph while keeping track how many of each letter you have visited. — n. 1.8e9-where's-my-share m., Dec 19 '16 at 10:56
Possible duplicate of [Algorithm to generate anagrams](http://stackoverflow.com/questions/55210/algorithm-to-generate-anagrams) — n. 1.8e9-where's-my-share m., Dec 19 '16 at 10:58
@n.m. So Does there exist any efficient algo to find all different cyclic paths? — Tony, Dec 19 '16 at 11:20
@Tony You just try them all one by one, in lexicographical order. — n. 1.8e9-where's-my-share m., Dec 19 '16 at 11:41
Yes, it is basically an anagram problem: http://stackoverflow.com/a/41226791/912829 — ACV, Dec 19 '16 at 16:15
@ACV yeah this is the problem we're trying to solve in the first place. — n. 1.8e9-where's-my-share m., Dec 20 '16 at 11:03
@n.m. The solution is here: http://stackoverflow.com/a/41226791/912829 — ACV, Dec 21 '16 at 13:16
@ACV It is a one-word anagram solution, completely trivial. We're talking about multi-word anagrams. — n. 1.8e9-where's-my-share m., Dec 21 '16 at 13:39
The task is not to just check whether few words are anagram or not, the task is to find sentences formed using same characters and combining valid words. I think the anagram solution mentioned above is not the required solution. — Vaibhav Arora, Dec 21 '16 at 15:35
Just a hint to help all is that according to the interviewer this is a complete data structure problem — Vaibhav Arora, Dec 21 '16 at 15:37

score 0 · Answer 1 · edited May 23 '17 at 11:45

As you have said, space doesn't count, so input can be just viewed as a list of chars. The output is the permutation of words, so an obvious way to do it is find all valid words then permutate them.

Now problem becomes to divide a list of chars into subsets which each forms a word, which you can find some answers here and following is my version to solve this sub-problem.

If the dictionary is not large, we can iterate dictionary to

find min_len/max_len of words, to estimate how many words we may have, i.e. how deep we recur
convert word into map to accelerate search;
filter the words which have impossible char (i.e. the char our input doesn't have) out;
if this word is subset of our input, we can find word recursively.

The following is pseudocode:

int maxDepth = input.length / min_len;

void findWord(List<Map<Character, Integer>> filteredDict, Map<Character, Integer> input, List<String> subsets, int level) {
  if (level < maxDepth) {
    for (Map<Character, Integer> word : filteredDict) {
      if (subset(input, word)) {
        subsets.add(word);
        findWord(filteredDict, removeSubset(input, word), subsets, level + 1);
      }
    }
  }
}

And then you can permutate words in a recursive functions easily.

Technically speaking, this solution can be O(n**d) -- where n is dictionary size and d is max depth. But if the input is not large and complex, we can still solve it in feasible time.

Valid Permutations of a String

1 Answers1