So I have a multidimensional array in java that holds a grid of characters. I am trying to match a string to characters in the grid. So far I have implemented searches for left to right, right to left, top to bottom, and bottom to top. They work, but not all the time.
The problem I am having is lets say for example I am searching for a string "ALGOS" which is in the grid from left to right. It finds an A, then finds another A, then finds an L, then stops. It should find an A, then L, G, O, S. The error I get is below:
A Found at: [0, 0]
A Found at: [1, 4]
L Found at: [1, 5]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8
at WordFind00.findWord(WordFind00.java:59)
at WordFind00.main(WordFind00.java:45)
Here is my code - what could be going wrong? Parts of it are commented out for testing each direction.
public static String findWord(char[][]board, String word) {
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[row].length; col++) {
if (board[row][col] == word.charAt(0)) {
// search to the right
for (int letters = 0; letters < word.length(); letters++) {
if (word.charAt(letters) == board[row][col+letters]) {
System.out.println(word.charAt(letters) + " Found at: " + Arrays.toString(new int[] {row,col+letters}));
}
} // end search to the right
/*// search to the left
for (int letters = 0; letters < word.length(); letters++) {
if (word.charAt(letters) == board[row][col-letters]) {
System.out.println(word.charAt(letters) + " Found at: " + Arrays.toString(new int[] {row,col-letters}));
}
} // end search to the left
// search down
for (int letters = 0; letters < word.length(); letters++) {
if (word.charAt(letters) == board[row+letters][col]) {
System.out.println(word.charAt(letters) + " Found at: " + Arrays.toString(new int[] {row+letters,col}));
}
} // end search down
// search up
for (int letters = 0; letters < word.length(); letters++) {
if (word.charAt(letters) == board[row-letters][col]) {
System.out.println(word.charAt(letters) + " Found at: " + Arrays.toString(new int[] {row-letters,col}));
}
} // end search down */
}
}
}
return null;
}
If anyone wants to test it: WordFind00.java: http://pastebin.com/DeNEQAsp input.dat: http://pastebin.com/WyYF3wPA
You are not checking the ranges of your array indicies, for example...
if (word.charAt(letters) == board[row][col-letters]) {
If col-letters is less than 0, this will throw an ArrayIndexOutOfBoundsException, this goes for each of your checks...
You could do something like...
if (col - word.length() >= 0) {
for (int letters = 0; letters < word.length(); letters++) {
if (word.charAt(letters) == board[row][col-letters]) {
System.out.println(word.charAt(letters) + " Found at: " + Arrays.toString(new int[] {row,col+letters}));
}
} // end search to the right
}
Which will ensure that the for-loop is only ever run if the col - word.length does not expand beyond the start of the array. If it does, then there's no real reason to attempt to even check the remaining cells.
You would need to apply this to all you conditions
Updated
The reason you're getting extract output is because the moment you find a matching character, you print it, regardless of whether you have a full match or not...here's a little cheat that will work for the horizontal checks...
String test = new String(board[row], col, word.length());
if (test.equals(word)) {
System.out.println("Found [" + word + "] @ " + row + "x" + col);
}
Alternatively, if you must you loops, you could do something like...
if (col + word.length() <= board[row].length) {
int letters = 0;
while (letters < word.length() && word.charAt(letters) == board[row][col + letters]) {
letters++;
}
if (letters == word.length()) {
System.out.println("Found [" + word + "] @ " + row + "x" + col);
}
}
Which basically checks to see if the number of matching characters equals the length of the original word or not...