Действительные перестановки строки

Question

Этот вопрос был задан мне в недавнем техническом интервью Amazon. Он выглядит следующим образом: -

Учитывая строку ex: «where am i» и словарь действительных слов, вы должны перечислить все допустимые различные перестановки строки. Правильная строка содержит слова, которые существуют в словаре. Например: «мы - он», «капризы» - это правильные строки, считающие слова (прихоть, ай) частью словаря. Также условие состоит в том, что простая перегруппировка слов не является допустимой строкой, то есть «я где» не является допустимой комбинацией.

Задача состоит в том, чтобы найти все возможные такие строки оптимальным образом.

Answer 1

Как вы сказали, пространство не считается, поэтому вход можно рассматривать только как список символов. Вывод - это перестановка слов, поэтому очевидный способ сделать это - найти все допустимые слова, а затем перестановить их.

Теперь проблема состоит в том, чтобы разделить список символов на подмножества, каждая из которых образует слово, которое вы можете найти в ответах here, а следующая - моя версия для решения этой подзадачи.

Если словарь не большой, мы можем перебирать словарь

• найти min_len/max_len слов, чтобы оценить, сколько слов мы можем иметь, то есть, насколько глубоко мы повторялись
• новообращенного слова в карту ускорить поиск;
• фильтровать слова, которые имеют невозможный символ (т. Е. Символ, который у нас нет);
• Если это слово является подмножеством нашего ввода, мы можем найти слово рекурсивно.

Ниже псевдокод:

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); 
     } 
    } 
    } 
} 

И тогда вы можете permutate слова в рекурсивной функции легко.

Технически это решение может быть O(n**d) - где n - размер словаря, а d - максимальная глубина. Но если вход не является большим и сложным, мы все равно можем решить его в допустимое время.