5

lすべての長さの正しい単語のリストと、同じく長さの誤った単語のリストが与えられた場合l、2つの連続する文字の交換によって、正しい単語のリストとは異なる誤った単語のリストから単語を見つけます。これらの単語はタイプミスと見なされます。たとえば、hteはタイプミスと見なされますが、タイプミスとは見なさtheれhetません。

この定義によってタイプミスと見なされる単語のリストを見つけることができる、最適な時間効率の高いアルゴリズムは何ですか？

リストは線形時間で計算される可能性があると知らされましたが、線形時間で解を見つけることができません。私が考えることができる唯一の方法は、あるリストのすべての文字を他のリストとブルートフォースで比較することです。

4

4 に答える 4

4 
L - list of correct words of size n.
L'- list of incorrect words of size m.
H - hash table
R - result set

1. for each word w in L :
   1.1  for each typo t of w : //there are l-1 typos
     1.1.1 insert t into H
2. for each word w' in L' :
   2.1 if w' in H insert w' in R
3. return R

時間計算量： O(n*l)+O(m) = O(max(n*l,m))

スペースの複雑さ： O(n*l)

于 2012-10-21T05:23:54.570 に答える
0

各「タイプミス」された単語に単一のスワップしか存在できないと仮定すると、次のようになります。

空のHashTableHから始めます。

誤った単語のリスト内の各単語Kについて：

  • 連続する文字の各ペアを交換することにより、（l-1）個の新しい単語を生成します：K_1、K_2、...、K_x、...、K_（l-1）
    • これらの新しい単語のそれぞれについて、キーをK_x、値をK（元の誤った単語）としてHashTableHに追加します。

ここで、正しい単語のリスト内の各単語Cについて、：

  • 各Cについて、キーCがHashTableHに存在するかどうかを確認します。
  • キーCがHashTableHに存在する場合は、Cに関連付けられた値C'を出力します。値はすべて元々誤った単語のリストからのものであるため、2つの連続する文字を交換することにより、正しい単語に変換した誤った単語を見つけたはずです。語。
  • そのような各C'を出力します

lは固定数であるため（そうでない場合は、lとnの両方を同時に無限大に増やすことができ、線形時間アルゴリズムはありません）、実行時の複雑さは次のようになります。

  • 間違った単語のリストを調べるには直線的な時間がかかります
  • 間違った単語リストの各単語に対して新しい単語を生成するには、一定の時間lがかかります
  • それぞれ（新しい単語、K）をHashTableHに追加するには一定の時間がかかります
  • 正しい単語リストを確認するには、直線的な時間がかかります
  • 正しい単語リストの各単語をHashTableHと照合するのに一定の時間がかかります

したがって、これはO（n）ランタイムです。

于 2012-10-21T05:22:21.623 に答える
0 
findTypos(List CORRECT_LIST,
List INCORRECT_LIST,
List TYPOS_OUTPUT_LIST) {
 boolean INCORRECT_LIST_EMPTY = false  

 for each element in CORRECT_LIST {  
    TYPOS = computeTypos(element)  
    for each typo in TYPOS  
        if(INCORRECT_LIST.contains(typo)) {  
            INCORRECT_LIST.remove(typo)  
            TYPOS_OUTPUT_LIST.add(typo)  
        }  
        if(INCORRECT_LIST.size() == 0) {  
            INCORRECT_LIST_EMPTY = true;  
            break;  
        }  
    }  
    if(INCORRECT_LIST_EMPTY) {  
        break;  
    }  
 }
 return TYPOS_OUTPUT_LIST;
}
于 2012-10-21T05:43:49.743 に答える
0

これがSINGLEスワップケースの解決策です。単語ごとにスワップは1つだけだと思います。つまり、単語のalgorithm場合、algo[ir]thmは有効なタイプミスです。while[la]go[ir]thmは無効です。

正しい単語リストAと他のリストを呼び出しましょうB。

  1. リストから誤った単語のハッシュテーブルを作成します。このようなハッシュ関数HBB
    Σ（a i * 10 i）; ここで、0 <= i <a.length、ai =インデックスiの文字のint値
    これはO(l)です。

2.で繰り返しAます。

（ベース1インデックスを想定）

タイプミス=[]
i=1からA.lengthの場合
  j = A[i].lengthの場合-2まで
    temp = swap（A [i]、j、j-1）
    hash = getHash（temp）
    if（H B .has（hash））
      typo.add（temp）
タイプミスを返す

2つのループが見えますか？彼らは何回実行しますか？数学をしましょう

a 1 .length + a 2 .length + .. + a l .length --l
（マイナスlは、実際には各単語で1つ少なく反復しているためです）
= length_of_all_characters_the_list_A --l

しかし、どうすれば注文できますか？さて、大きなOは上限なので、

O（l * max（A [i] .length）
=> O（l * m）
于 2012-10-21T05:47:43.357 に答える