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!");
           }
       }
   }
}

I would probably do this with iteration not recursion. I say this because there seems to be a lot of corner cases and the amount of information that you would have to pass to your recursive function would get unwieldy. I.e. at first you just want to check if the letter your at is the first in the word, then you check for letters around it that come next, and then after that you need to proceed in the same direction the first 2 letters set you in. It is certainly possible but iteration seems to be the way in my book. — kpie
– kpie, Commented Oct 11, 2016 at 18:11

Nicolas Filotto · Accepted Answer · 2016-10-11 18:30:57Z

1

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

answered Oct 11, 2016 at 18:30

Nicolas Filotto

45.3k11 gold badges97 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Work of Artiz · Accepted Answer · 2016-10-11 19:24:23Z

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.

Collectives™ on Stack Overflow

Recursive array search of char array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related