メソッドなしの2D文字配列内の文字列の検索

Question

他の学生のための演習をテストするのは私の仕事です。今日私は本当に難しい（少なくとも私のために）私はちょうど今のブロックヘッドかどうかは分かりません。

私はそこで見つけなければならない2D char配列と3つの文字列を得ました。単語は水平、垂直、斜めにまたがることができます。前方または後方。問題：私はすべてのメソッドを使用することはできません、すべてがメインメソッドの内部にある必要があります。

私は好きではない方法を見つけません< 10ループ。スマートなアイデアはありますか？

Answer 1

私が意味する、これは明白な方法で、もちろん...

比較はわずかBoyer-Mooreまたは類似してスピードアップすることができます。

for row in haystack: 
    for character in row: 
    #check if pattern or reversed pattern matches 
for column in haystack: 
    for character in column: 
    #check if pattern or reversed pattern matches 
for positively-sloped-diagonal in haystack: 
    for character in diagonal: 
    #check 
for negatively-sloped-diagonal in haystack: 
    for character in diagonal: 
    #check 

は正確なパラメータの種類によっては、それはのような何かをするために少し小さい脳死のようになります。

for each pattern: 
    for each slot in the array: 
    for horizontal in [-1, 0, 1]: 
     for vertical in [-1, 0, 1]: 
     if horizontal == vertical == 0: 
      pass 
     for n in range(pattern.length): 
      if pattern[n] != haystack[row + n * vertical][column + n * horizontal] 
      break 
     #Pattern found 
    #Pattern not found 

Answer 2

あなたは再帰的に前方、後方、アップ、ダウン検索するmainメソッドを呼び出すことができ、左上/下斜め、右上/下斜めに表示されます。

if (arg[2] == array.length && arg[3] == array.length) 
    return 0; 

if (firstTimeMainFunctionCalled) { 
    for (int i = 0; i < array.length; i++) { 
     for (int j = 0; j < array[0].length; j++) { 

      // Only make recursive call when you are 
      // on the outer edge of the 2D array 
      if (i == 0 || j == 0) { 
       main(1, 0, i, j); 
       main(0, 1, i, j); 
       main(1, 1, i, j); 
       main(-1, 0, i, j); 
       main(0, -1, i, j); 
       main(-1, -1, i, j); 
       main(1, -1, i, j); 
       main(-1, 1, i, j); 
     } 
    } 
} 

int rowInc = arg[0]; 
int colInc = arg[1]; 
int curRow = arg[2]; 
int curCol = arg[3]; 
int str1Place = 0; 
int str2Place = 0; 
int str3Place = 0; 

while (curRow >= 0 && curCol >= 0 && curRow < array.length && curCol < array[0].length) { 
    if (array[curRow][curCol] == str1[str1Place]) 
     str1Place++; 
    else 
     str1Place = 0; 

    if (str1Place == str1.length) 
     // Found str1 

    // Do the same for str2 and str3 

    curRow += rowInc; 
    curCol += colInc; 
} 

これは非常に粗溶液で、全体の多くを向上させることができ、あなたは明らかに文字列のリストに引数を回すことによって、適切にmainメソッドを呼び出す必要がありますが、それは起動にどこかを与える必要があります。あなたは動的プログラミングを使用してこれを改善することができます、あなたはまた、一度それを見つけると文字列で何かをするためにバックトラックすることができます。また、ネストしたループをネストする必要はありません。

私の擬似コード：