Recursive array search of char array

Question

I am trying to figure out how to recursively search a char array for a word and return if it is or isn't present. Think of it like the programming equivalent of a word search. My current code is below. Seed value of 9999 is helpful for testing. How do I write a recursive search method to verify any given word's presence in a char array?

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

Here is my main 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

So I guess the question was for a recursive string match, which although pointed out earlier might not be the best way to go about it still can be used.

Looking at your code, you don't want to match against a char array, but rather a char matrix. Let's take the naive approach since we're on an inefficient path anyway.

I'll give some pseudo code, let's start with some code that checks whether the matrix matches the array at a certain 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

Now this is still not a recursive solution, and the function has a lot of arguments (not great for code clarity). Let's first write a wrapper:

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

The recursiveMatches has to keep track of it's original row and column, to make a proper recursive call. And ofcourse it needs a recursive call where it would fail before:

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

Converting this to proper java code shouldn't prove too difficult I hope.

Answer 2

The simplest way to find a word in a char array is probably to convert it first into a String, then use contains as next no need to reinvent the wheel:

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

This is the most basic way which is case sensitive and will return true if the word is only a subpart of a bigger word, so something more appropriate would be to use matches with a case insensitive regular expression that defines the word boundaries as below:

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