文字列（再帰/バイナリ検索）が与えられたときにすべての有効な単語を見つける

Question

私が実装しようとした方法についてのフィードバックが100％でないとします。私は、ユーザーに20のランダムな文字が与えられている練習用のAndroidアプリを作っています。ユーザーは、これらの文字を使用して、どんなサイズの単語を作成します。次に、辞書が有効な英語の単語であるかどうかを調べます。 私に問題を起こす部分は、「ヒント」を表示することです。ユーザーが立ち往生している場合は、可能な単語を表示します。私は当初、再帰を考えました。しかし、20文字の場合、実行にはかなりの時間がかかります。そこで、バイナリ検索を実装して、現在の再帰パスが辞書内のすべてのプレフィックスであるかどうかを確認しました。私は有効なヒントを得て出力しますが、すべての可能な単語を返すわけではありません。私は再帰思考でここに間違いがありますか？また、推奨されているより高速のアルゴリズムがありますか？私はあなたが辞書の各単語をチェックし、その文字が各単語を作ることができるかどうかを調べる方法を見てきました。しかし、私の方法がそれに対してどれほど効果的かを知りたい。

private static void getAllWords(String letterPool, String currWord) { 
    //Add to possibleWords when valid word 
    if (letterPool.equals("")) { 
     //System.out.println(""); 
    } else if(currWord.equals("")){ 
     for (int i = 0; i < letterPool.length(); i++) { 
      String curr = letterPool.substring(i, i+1); 
      String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1)); 
      if(dict.contains(curr)){ 
       possibleWords.add(curr); 
      } 

      boolean prefixInDic = binarySearch(curr); 
      if(!prefixInDic){ 
       break; 
      } else { 
       getAllWords(newLetterPool, curr); 
      } 
     } 
    } else { 
     //Every time we add a letter to currWord, delete from letterPool 
     //Attach new letter to curr and then check if in dict 
     for(int i=0; i<letterPool.length(); i++){ 
      String curr = currWord + letterPool.substring(i, i+1); 
      String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1)); 
      if(dict.contains(curr)) { 
       possibleWords.add(curr); 
      } 
      boolean prefixInDic = binarySearch(curr); 
      if(!prefixInDic){ 
       break; 
      } else { 
       getAllWords(newLetterPool, curr); 
      } 
     } 
    } 

private static boolean binarySearch(String word){ 
    int max = dict.size() - 1; 
    int min = 0; 
    int currIndex = 0; 
    boolean result = false; 
    while(min <= max) { 
     currIndex = (min + max)/2; 
     if (dict.get(currIndex).startsWith(word)) { 
      result = true; 
      break; 
     } else if (dict.get(currIndex).compareTo(word) < 0) { 
      min = currIndex + 1; 
     } else if(dict.get(currIndex).compareTo(word) > 0){ 
      max = currIndex - 1; 
     } else { 
      result = true; 
      break; 
     } 
    } 
    return result; 
} 

Answer 1

あなたのアルゴリズムを高速化するための最も簡単な方法は、

トライデータ構造は、2つの関連するメソッドを提供しますTrie（プレフィックスツリー）を使用することが考えられます。 isWord（String）およびisPrefix（String）。どちらもO（n）比較を使用して、単語または接頭辞が辞書内に存在するかどうかを判定します（nは引数の文字数）。あなたの辞書の大きさは関係ありませんので、これは本当に速いです。

バイナリ検索でプレフィックスが存在するかどうかをチェックする方法は、O（n * log（m））です.nは文字列の文字数、mは辞書。

Trieを使用して同様のアルゴリズムをコーディングし、非常に非公式のベンチマークで投稿したコード（マイナーな変更を加えたもの）と比較しました。 20文字の入力で、Trieは9msかかりました。私はそれを殺さなければならなかったので、元のコードは妥当な時間に完了しませんでした。

編集： あなたのコードがすべてのヒントを返さない理由については、プレフィックスがあなたのdictにない場合、あなたは壊れたくありません。代わりに次のプレフィックスを確認してください。

Answer 2

推奨、より高速なアルゴリズムがありますか？

は、「パターンの有限集合は、」あなたの辞書である「Algorithms using a finite set of patterns」という名前の特定のセクションで、「String searching algorithm」のWikipediaの記事を参照してください。

Aho–Corasick algorithmが最初に表示される場合があります。