Rekursive Array-Suche von Char-Array

Question

Ich versuche herauszufinden, wie ein Char-Array für ein Wort rekursiv suchen und zurückgeben, wenn es oder nicht vorhanden ist. Stellen Sie es sich vor wie das Programmieräquivalent einer Wortsuche. Mein aktueller Code ist unten. Der Startwert von 9999 ist hilfreich beim Testen. Wie schreibe ich eine rekursive Suchmethode, um die Anwesenheit eines gegebenen Wortes in einem char-Array zu überprüfen?

public class Board { 

    private char[][] board = new char[4][4]; 
    private boolean[][] visited = new boolean[4][4]; 
    private String word; 

    public Board(int seed){ 
     word = ""; 
     Random rand = new Random(seed); 

     for(int i = 0; i < board.length; i++){ 
      for(int j = 0; j < board[0].length; j++){ 
       char randomChar = (char) (rand.nextInt(27) + 65); 
       //System.out.print(" " + randomChar + " "); 
       board[i][j] = randomChar; 
       //System.out.print(board[i][j]); 
      }//System.out.println(); 
     }  
    } 

    public void resetBoard(){ 
     for(int i = 0; i < board.length; i++){ 
      for(int j = 0; j < board[0].length; j++){ 
       visited[i][j] = false; 
      } 
     } 
    } 

    public void printBoard(){ 
     for(int i = 0; i < board.length; i++){ 
      for(int j = 0; j < board[0].length; j++){ 
       if(j == 0) 
        System.out.println("+---+ +---+ +---+ +---+"); 
       System.out.print("| " + board[i][j] + " | "); 
      } 
      System.out.println("\n+---+ +---+ +---+ +---+"); 
     } 
    } 

    public boolean verifyWord(String w){ 
     this.word = w; 
     for(int i = 0; i < w.length(); i++){ 
//   char letter = w.charAt(i); 
//   System.out.println(letter); 
      boolean wordVerify = verifyWordRecursively(0, 0, 0); 
      if(wordVerify == true) 
       return true; 
//   if(i == w.length() - 1){ 
//    if(wordVerify == true) 
//     return true; 
//   } 
     }return false; 
    } 

    public boolean verifyWordRecursively(int wordIndex, int row, int col){ 
     char letter = word.charAt(wordIndex); 
     System.out.println(letter); 
     if(board[row][col] == letter){ 
      return true; 
     } 
     else{ 
      if(col + 1 < board[0].length){ 
       verifyWordRecursively(wordIndex, row, col + 1); 
      } 
      if(row + 1 < board.length){ 
       verifyWordRecursively(wordIndex, row + 1, col); 
      } 
     }return false; 
    } 
} 

Hier ist meine Hauptklasse:

public class LA2Main { 

    public static void main(String[] args) throws IOException{ 
     int seed = getSeed(); 
     Board b = new Board(seed); 
     b.printBoard(); 

     Scanner inFile = new Scanner(new FileReader("input.txt")); 
//  while(inFile.hasNextLine()){ 
//   System.out.println(inFile.nextLine()); 
      String word = inFile.nextLine(); 
      b.resetBoard(); 
      System.out.println("-----------------------\n" + word); 
      boolean isVerified = b.verifyWord(word); 
      if(isVerified == true) 
       System.out.println("'" + word + "' was found on the board!"); 
      else 
       System.out.println("'" + word + "' is NOT on this board"); 
      b.printBoard(); 
//  } 
    } 

    public static int getSeed(){ 
     Scanner sc = new Scanner(System.in); 
     int userInput; 
     while(true){               
      try{ 
       System.out.println("Enter an integer seed value greater than 0: "); 
       userInput = Integer.parseInt(sc.next()); 
       if(userInput > 0) 
        return userInput; 
      } 
      catch(NumberFormatException e){ 
       System.out.println("Invalid!"); 
      } 
     } 
    } 
} 

Answer 1

Der einfachste Weg, ein Wort in einem char-Array zu finden wahrscheinlich in ein String zuerst zu konvertieren, dann contains verwendet als nächstes keine Notwendigkeit

boolean contains = new String(myCharArray).contains(myWord); 

Dies ist der einfachste Weg: das Rad neu zu erfinden was ist case sensitive und kehren true wenn das Wort nur ein Unterpunkt eines größeren Wortes, so etwas besser geeignet wäre matches mit einem Fall unempfindlich regulären Ausdruck zu verwenden, wie unten die Wortgrenzen definiert:

boolean contains = new String(myCharArray).matches(
    String.format("(?i)^.*\\b%s\\b.*$", Pattern.quote(myWord)) 
); 

Answer 2

Also ich denke, die Frage war für eine rekursive String-Match, die, obwohl früher darauf hingewiesen, möglicherweise nicht der beste Weg, um darüber zu gehen, noch verwendet werden kann.

Mit Blick auf Ihren Code möchten Sie nicht mit einem Char-Array, sondern eine Char-Matrix übereinstimmen. Nehmen wir den naiven Ansatz, da wir ohnehin auf einem ineffizienten Weg sind.

Ich werde einige Pseudo-Code geben, lassen Sie uns mit einigen Code starten, der die Matrix überprüft, ob das Array entspricht bei einem bestimmten Offset:

function matches(char matrix[][], char needle[], int row, int col) 
    width, height = dimensions(matrix) 

    /* Check whether we're out of range */ 
    if (width * height < row * width + col + length(needle)) { 
     return false 
    } 

    for (int i = 0 ... len(needle)) { 
     if (matrix[row][col] != needle[i]) { 
      return false 
     } 

     /* increment position, (hint: integer division) */ 
     row += (col + 1)/width 
     col = (col + 1) % width 
    } 

    return true 

Nun ist dies noch nicht eine rekursive Lösung, und die Funktion hat viele Argumente (nicht gut für Code Klarheit). Lassen Sie sich zunächst einen Wrapper schreiben:

function matches(char matrix[][], char needle[]) 
    recursiveMatches(matrix, needle, 0, 0) 

Die recursiveMatches Strecke zu halten hat es ursprüngliche Zeile und Spalte sind, einen richtigen rekursiven Aufruf zu machen. Und natürlich braucht es einen rekursiven Aufruf, wo es scheitern würde vor:

function recursiveMatches(char matrix[][], char needle[], int row, int col) 
    width, height = dimensions(matrix) 
    originalRow, originalCol = row, col 

    /* Check whether we're out of range */ 
    if (width * height < row * width + col + length(needle)) { 
     return false 
    } 

    for (int i = 0 ... len(needle)) { 
     if (matrix[row][col] != needle[i]) { 
      /* add one to the position */ 
      originalRow += (originalCol + 1)/width 
      originalCol = (originalCol + 1) % width 
      return recursiveMatches(matrix, needle, originalRow, originalCol) 
     } 

     /* increment position */ 
     row += (col + 1)/width 
     col = (col + 1) % width 
    } 

    return true 

diese Umstellung auf die richtige Java-Code sollte nicht zu schwierig erweisen, wie ich hoffe.