Suche nach Strings in einem 2D-Char-Array ohne Methoden

Question

Es ist meine Aufgabe, Übungen für andere Schüler zu testen. Heute habe ich einen wirklich schwierigen (zumindest für mich) und ich bin mir nicht sicher, ob ich gerade ein Dummkopf bin.

Ich habe ein 2D-Char-Array und 3 Strings, die ich dort finden muss. Die Wörter können horizontal, vertikal und diagonal sein; vorwärts oder rückwärts. Das Problem: Ich darf keine Methoden verwenden, alles muss innerhalb der Hauptmethode sein.

Ich finde keinen Weg, der nicht wie < 10 Schleifen hat. Hast du eine kluge Idee?

Answer 1

ich meine, das ist die offensichtliche Art und Weise, natürlich ...

Vergleiche konnten leicht mit Boyer-Moore oder ähnlichem beschleunigt werden.

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 

Je nach dem genauen Parameter, könnte es ein bisschen weniger hirntot sein, um so etwas wie:

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

Sie können das Hauptverfahren rekursiv Rufweiterleitung zu suchen, rückwärts, nach oben, nach unten, links-oben/unten-diagonal und rechts-oben/unten-diagonal.

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

Dies ist eine sehr rohe Lösung und kann eine ganze Menge verbessert werden, haben Sie natürlich in geeigneter Weise die Haupt-Methode aufrufen, indem Sie die Argumente in eine Liste von Strings drehen, aber es sollte man irgendwo anfangen geben. Sie können dies mit dynamischer Programmierung verbessern, Sie können auch eine Rückverfolgung durchführen, um etwas mit der Zeichenfolge zu tun, sobald Sie sie gefunden haben. Wie Sie sehen können, muss die verschachtelte Schleife nicht verschachtelt sein.

Pardon mein Pseudo-Code :)