java - char数组的递归数组搜索

Question

我试图弄清楚如何递归地搜索字符数组中的单词并返回它是否存在。把它想象成相当于单词搜索的编程。我当前的代码如下。种子值 9999 对于测试很有帮助。如何编写递归搜索方法来验证字符数组中是否存在给定单词？

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

这是我的主要类(class):

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

这是最基本的方法，它区分大小写，并且如果该单词只是一个子部分，则返回true更大的词，所以更合适的是使用 matches使用不区分大小写的正则表达式定义单词边界，如下所示:

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