1

したがって、ダイヤルパッドの各番号に割り当てられた文字を使用して、電話番号で綴ることができるすべての可能な組み合わせを見つける必要があります。すなわち：2226262は「ABANANA」を綴ることができます。

8未満の任意の長さの任意の数を指定すると、整数に一致するすべての単語を見つけることができます。つまりfindWholeWord(dictionary[2], 723)、文字列の配列を教えてくれます{"RAD", "RAE", "RAF", "SAD", "SBF", "PAE", "PAD"}（私が与えられた辞書はちょっとばかげています...）。私の辞書は7つの部分に分かれており、各部分には同じ長さの単語が含まれています。

私がよくわからないのは、7桁の数字を取り、1つの単語の長さ6、1つの単語の長さ1（6、1）、5と2、5と1と1、4と3、4のようなすべての単語の組み合わせを与える方法です2と1。単語全体をカバーしていないもの（0または1、3文字と2文字の単語で、最後の2文字に一致しないもの）をすべて破棄したい。この論理をどうやって進めるのかわかりません。この種のロジックには、木を描いてパターンがいいので名前が付いていると思いますが、そのパターンが何と呼ばれているのか、正確には何と呼ばれているのかわかりません。

1つの方法は、すべてのサブワードを見つけて、機能する方法でそれらを組み合わせようとすることです。もう1つの方法は、単語の長さのすべての可能な組み合わせを試すことです：（7）、（6,1）、（5,2）、（ 5,1,1）、（4,3）、（4,2,1）、（4,1,2）、（4,1,1,1）など..

どちらを行うかわからない、どちらが簡単かわからない、どちらが最も効率的かわからない。

4

2 に答える 2

0

解決策を考えることはできますが、これらの辞書が実行時に更新されるか、開発時に修正されるかによって異なります。これらの辞書が時間の経過とともに変化しない場合は、次のようにすることができます。

  1. 使用している辞書に対して前処理タスクを実行します。これにより、すべての辞書のすべての単語に対して、いくつかの単純なデータ構造で同等の番号を作成します（つまり、「BANANA」の場合は「226262」を指定します）。
  2. これらの辞書は、「Word」フィールドでインデックス付けされた7つのテーブル（単語の長さごとのテーブル）のデータベースに保存して、実行時にプログラムで再度読み取ることができるようにします。
  3. 指定された番号「2226262」を取り、StringArrayListを返すメソッドを作成します。N=1から7の場合; 最初のN桁を取得し、使用している桁を使用して「Nテーブル」内の可能な単語を検索します。取得した可能性のあるすべての単語について、すべての単語の残りの数字を使用して同じメソッドを再度呼び出します（つまり、単語が3文字の場合は、最後の4桁を使用してメソッドを呼び出します）。新しいStringArrayListを作成し、これらの呼び出しから取得したすべての結果を後で追加して、それを返します。
  4. 「無限再帰」を回避するために、この再帰の終了条件を必ず作成してください。メソッドの最初で、指定された数値が長さがゼロかどうかを確認することをお勧めします。そうである場合は、空のStringArrayListを返すだけです。

私の主張を明確にしたいと思います

アップデート

これが私が言っていることのsudoコードです：

ArrayList<String> getWordsOf(String Number){
    if(Number.isEmpty()){
        return new ArrayList<String>();
    }
    ArrayList<String> allPossibleWords = new ArrayList<String>();
    for(int i=1; i<=Number.length(); i++){
        ArrayList<String> possibleWords = getFromDataBase(Number.substring(0,i));
        ArrayList<String> restOfPossibleWords = getWordsOf(Number.substring(i,Number.length()-i));
        for(String possibleWord:possibleWords){
            for(String restOfPossibleWord:restOfPossibleWords){
                allPossibleWords.add(possibleWord+" "+restOfPossibleWord);
            }
        }
    }
    return allPossibleWords;
}
于 2012-11-26T06:36:09.540 に答える
0

考えられるすべての組み合わせを試す代わりに、インデックスごとに取得した単語の数を数えておけば、時間を節約できます。findWholeWord(dictionary[2], 723); wordCount[2]=7; 分かりやすくするために('A' 以外の 1 文字の単語は考えられません)、これは、7X7 の代わりにwordCount[0]=1; wordCount[5]=3;1X3 の組み合わせだけを実行する必要があることを意味します。サブワードのマッチングにかなりの時間を節約できます。

于 2012-11-26T06:38:24.007 に答える