文字配列の再帰配列検索

Question

単語の文字配列を再帰的に検索し、存在するかどうかを返す方法を見つけようとしています。それを単語検索と同等のプログラミングと考えることができます。私の現在のコードは以下の通りです。 9999のシード値はテストに役立ちます。どのように再帰的な検索メソッドを記述して、指定された単語がchar配列に存在するかを確認するにはどうすればよいですか？ここで

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

は私のメインクラスです：char配列に単語を見つけるため

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

最も簡単な方法は、Stringに最初にそれを変換するために、おそらく、その後、として次の必要性を全くcontainsを使用していませんこれは、最も基本的な方法ある

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

：車輪の再発明しますこれcase sensitiveで、単語が大きな単語の唯一のサブパートであるので、より適切なものは以下のように単語の境界を定義する大文字小文字を区別しない正規表現でmatchesを用いることであろう場合trueを返します。

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

Answer 2

私は質問が再帰的な文字列の一致であったと推測しますが、それは先に指摘したが、それを使う最良の方法ではないかもしれないが、まだ使用できる。

コードを見ると、文字配列と照合するのではなく、文字行列と照合する必要があります。とにかく非効率的な道を歩んでいるので、素朴なアプローチをとってみましょう。

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 

を今これはまだ再帰的な解決策ではなく、機能があります。

私はのは、行列が一定のオフセットで配列に一致するかどうかをチェックするいくつかのコードから始めましょう、いくつかの擬似コードをあげます多くの議論があります（コードの明快さにはあまり適していません）。のは、最初のラッパーを書いてみましょう：

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

recursiveMatchesは、適切な再帰呼び出しを行うために、元の行と列、 だそれを追跡する必要があります。そしてofcourseのそれが前に失敗する再帰呼び出しを必要とします：

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 

適切なJavaコードにこれを変換する私が期待しすぎて難しいかもべきではありません。