在沒有任何方法的情況下搜索2D Char字符串中的字符串

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

您可以遞歸調用的主要方法搜索前進，後退，上升，下降，左上/下對角線，右上/下對角線。

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; 
} 

這是一種非常原始的解決方案，可以提高一大堆，你顯然需要通過轉動參數到字符串列表適當地調用的主要方法，但它應該給你的地方開始。您可以使用動態編程來改善這一點，您也可以在找到該字符串時對其進行回溯處理。另外，正如你所看到的，嵌套循環不需要嵌套。

請原諒我的僞代碼:)