2016-12-18 6 views
1

この質問は、最近のアマゾンの技術的インタビューで私に尋ねられました。次のようになります。 -有効な文字列の置換

「where am i」と有効な単語の辞書を指定すると、その文字列の有効な別個の順列をすべてリストする必要があります。有効な文字列は、辞書内に存在する単語からなる。例:「私たちは彼です」、「気まぐれ」は辞書の一部であることを考慮して有効な文字列です。また、単語の単なる並べ替えは有効な文字列ではない、すなわち「私はどこにいる」が有効な組み合わせではないという条件もある。

この作業は、可能な限りすべての文字列を最適な方法で検索することです。

+1

このインタビューの質問にお答えしようとしましたか?もしそうなら、すでに持っているコードを共有できますか? –

+0

@TimBiegeleisen私は、文字列のさまざまな順列を生成し、各順列が動的プログラミングを使用して有効な単語に分解できるかどうかを調べることを考えました。 –

+0

スペースに文字列が含まれていますか? – Tony

答えて

0

あなたが言ったように、スペースはカウントされないので、入力は単に文字のリストとして見ることができます。出力は単語の順列であるので、それを行う明白な方法は、すべての有効な単語を見つけて、それらを並べ替えることです。

ここで問題は、文字のリストをそれぞれの単語を構成するサブセットに分割することです。答えはhereです。このサブ問題を解決するためのバージョンは次のとおりです。辞書が大きくない場合

することは、我々はマップに

  • 変換ワードを再発どのように深いつまり、我々が持っているかもしれどのように多くの単語を推定するために、言葉のmin_len/MAX_LENを見つける

    • に辞書を反復処理することができます検索を高速化する。
    • 不可能なcharを持つ単語(つまり、入力にはないchar)をフィルタリングします。
    • この単語が入力のサブセットであれば、単語を再帰的に見つけることができます。

    次は擬似コードです:

    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は最大の深さです。しかし、入力が大きく複雑でない場合でも、実現可能な時間で入力を解決できます。