字符串的有效排列

Question

在最近的亞馬遜技術訪談中，這個問題被問到了我。它如下： -

給定一個字符串ex：「我在哪裏」和一個有效單詞字典，你必須列出字符串的所有有效的不同排列。有效的字符串包含字典中存在的單詞。例如：「我們是他」，「思念」是有效的字符串，考慮到單詞（怪異，蜜蜂）是詞典的一部分。此外，條件是單純的重新排列不是一個有效的字符串，即「我在哪裏」不是有效的組合。

任務是以最佳方式找到所有可能的字符串。

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

然後你就可以輕鬆地重排列的遞歸函數的話。

從技術上講，這個解決方案可以是O(n**d)-其中n是字典大小，d是最大深度。但是，如果投入不是很大和複雜，我們仍然可以在可行的時間內解決它。