文字のリスト内の単語を検索

Question

私はオンラインで自己学習する宿題の合計を持っています： 文字のリスト内の単語を検索します。

eg Input: COOL 
List of characters: {A,B,C,O,L,M,O,L,F} return true 
Input : Book 
List of characters: {A,B,C,O,L,M,O,L,F} return false (as K is not present). 
Note: C found at index 2, then O should be found at index > 2 (Linear searching, search from left to right). 

I could think of two solutions, both brute force. 
1. Using Brute force approach to get the output 
2. Using Recursion (not sure if this approach is right, however, I am expected to solve it using dynamic programming). 

ダイナミックプログラミングの専門家ではないので、私に同行してください。 私が思いついた解決策：私は、このソリューションが動作することを確認していないIDE上でそれを試してみる必要がある

public boolean found(final String input,int n, boolean isFound, int a, String words) { 

    if(n == input.length) { 
     return isFound; 
    } 

char charValue = input.charAt(n); 

for(int i = a; i<words.length-1; i++) { 

    if(charValue == words.charAt[i]) { 
     isFound = true; 
    return found(input, n+1, true, i+1; words); 
    }else { 
    isFound = false; 
    } 
} 

    return isFound; 
} 

。しかし、私はこれが動的プログラミングで解決されることを期待しています。私は、キャッシュ/メモリに入力を保存して、再び使用することができる場所がわかりません。

Answer 1

なぜ動的プログラミングを行うのですか？入力語が文字のリストに存在するかどうかを調べたい私はあなたにシンプルで効率的なアプローチを提供します。

bool is_word_present(string word, vector<char> word_list){ 
    int word_index = 0; 
    int word_list_size = word_list.size(); 
    int word_len = word.length(); 
    for(int i = 0; i < word_list_size && word_index < word_len; i++){ 
     if(word_list[i] == word[word_index]){ 
      word_index++; 
     } 
    } 
    return word_index == word_len; 
} 

質問はjavaコードを持っており、私はここC++コードを与えました。しかし、問題のアルゴリズムの部分に興味があるように見えるので重要ではありません。さらに、コードは自明です。

時間の複雑さ：O（n）ここで、nは文字のリスト内の要素の数です。

空間の複雑さ：O（1）。

Answer 2

ファイルからのリスト（Oxford Dictionaryなど）をリストに読み込みます。

このリストから単語を削除するので、最後のインデックス（長さ-1）から最初の単語までループします。

このループの中には、単語の各文字を通る内部ループがあります。現在の文字が許可された文字のリストにない場合、リストから単語を削除し、内側のループから抜け出します。

私は動的プログラミングの問題としてこれを実際には認識しません。あなたが本の中のすべての単語をチェックしていたら、パスハッシュセットまたは失敗ハッシュセットでチェックする各単語を保存して、各文字を処理する前にそれを調べることができます。 ）。この場合、文字列のハッシュを作成すると、すべての文字が読み込まれる必要があるため、スピードを落とすことはできません。

C＃では、単一のLINQ文でこれを簡単に達成できます。

void Main() 
{ 
    string[] wordsToProcess = new string[] { "one", "two", "three", "bad", "cat", "dog" }; 
    char[] charactersToAllow = new char[] { 'a', 'b', 'c', 'd', 'e', 't', 'o', 'g' }; 
    List<string> qualifyingWords = 
     wordsToProcess 
      .Where(w => w.All(c => charactersToAllow.Contains(c))) 
      .ToList(); 
    qualifyingWords.ForEach(Console.WriteLine); 
}