In this post we will tackle the LeetCode 79 Word Search problem using the Java programming language.
Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Constraints: o m == board.length o n = board[i].length o 1 <= m, n <= 6 o 1 <= word.length <= 15 o board and word consists of only `lowercase` and `uppercase` English letters. Related Topics: o Array o Backtracking o Matrix
We are given a grid (or two dimensional array) of characters and a string `word`. Our task is to determine if we can find the specified `word` in the matrix following the specified rules.
It looks to me like a depth first search problem.
If interested in this problem I suggest you read the current description of the problem on the LeetCode website to make sure the description has not been updated or if I omitted an important detail.
public boolean exist(char[][] board, String word) {
}
The signature for the function of interest seems like a good match to the requirements. We are given a `board` of characters and a string `word` and we need to return `true` or `false` if we found or not the `word` in the `board`.
I will be solving the problem using Java and the VSCode IDE on a Windows computer. Unless you have a specific need, I suggest solving the problem using the online IDE provided by LeetCode. I want to keep the solution and the test code together, so I will have to develop a test scaffold which IS NOT PART OF THE SOLUTION!
2 2 "C","A" "L","L" "CALL" main <<< rows: 2 main <<< cols: 2 main <<< board: C, A L, L main <<< word ==>CALL<== len: 4 main <<< exist: true main <<< rows: 2 main <<< cols: 2 main <<< board: C, A L, L main <<< word ==>CALL<== len: 4 main <<< exist0: true main <<< exist: true 3 4 "A","B","C","E" "S","F","C","S" "A","D","E","E" "ABCCED" main <<< rows: 3 main <<< cols: 4 main <<< board: A, B, C, E S, F, C, S A, D, E, E main <<< word ==>ABCCED<== len: 6 main <<< exist0: true main <<< exist: true 3 4 "A","B","C","E" "S","F","C","S" "A","D","E","E" "SEE" main <<< rows: 3 main <<< cols: 4 main <<< board: A, B, C, E S, F, C, S A, D, E, E main <<< word ==>SEE<== len: 3 main <<< exist0: true main <<< exist: true 3 4 "A","B","C","E" "S","F","C","S" "A","D","E","E" "ABCB" main <<< rows: 3 main <<< cols: 4 main <<< board: A, B, C, E S, F, C, S A, D, E, E main <<< word ==>ABCB<== len: 4 main <<< exist0: false main <<< exist: false 3 5 "a","O","B","S","E" "b","N","J","A","M" "c","D","0","0","7" "JAMESBOND007" main <<< rows: 3 main <<< cols: 5 main <<< board: a, O, B, S, E b, N, J, A, M c, D, 0, 0, 7 main <<< word ==>JAMESBOND007<== len: 12 main <<< exist0: true main <<< exist: true 2 2 "O","O" "O","G" "GO" main <<< rows: 2 main <<< cols: 2 main <<< board: O, O O, G main <<< word ==>GO<== len: 2 main <<< exist0: true main <<< exist: true 3 4 "A","B","C","E" "S","F","E","S" "A","D","E","E" "ABCEFSADEESE" main <<< rows: 3 main <<< cols: 4 main <<< board: A, B, C, E S, F, E, S A, D, E, E main <<< word ==>ABCEFSADEESE<== len: 12 main <<< exist0: true main <<< exist: true
Each test case is separated from the next by two blank lines.
The first few lines are inputs to the test scaffold. The first two lines contain the dimensions of the `board`. The next lines contain the characters for each row in the board. The last input line holds the `word` that we need to look for in the `board`.
After the test code reads the input lines it displays the number of rows and columns in the `board`. The contents of the `board` are then displayed. Then the contents of the `word` are displayed. This is done to make sure all is well before calling the function of interest.
It seems that we have two implementations. They are called one after the other and the results are displayed.
/**
* Test scaffold
* !!! NOT PART OF THE SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of rows `rows` ****
int rows = Integer.parseInt(br.readLine().trim());
// **** read number of columns `cols` ****
int cols = Integer.parseInt(br.readLine().trim());
// **** create `board` ****
char[][] board = new char[rows][cols];
// **** read `board` contents ****
for (int r = 0; r < rows; r++) {
// **** read next row into Character[] row ****
Character[] row = Arrays.stream(br.readLine().trim().split(","))
.map( x -> x.charAt(1) )
.toArray(Character[]::new);
// **** copy Character[] row to char[] board[r] ****
int c = 0;
for (Object ch : row)
board[r] = (char)ch;
}
// **** read `word` (remove start and end double quotes ****
String word = br.readLine().trim().replaceAll("^\"|\"$", "");
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< rows: " + rows);
System.out.println("main <<< cols: " + cols);
System.out.println("main <<< board:");
System.out.println(displayBoard(board));
System.out.println("main <<< word ==>" + word + "<== len: " + word.length());
// **** call function of interest and display result ****
System.out.println("main <<< exist0: " + exist0(board, word));
// **** call function of interest and display result ****
System.out.println("main <<< exist: " + exist(board, word));
}
The test code uses a buffered reader to read the input lines. It allocates and populates the `board` and `word` arguments used by the two implementations of the function of interest. The two implementations are called and the returned value for each is displayed.
Please keep in mind that the test code IS NOT PART OF THE SOLUTION!
// **** global variables (should be converted to arguments) ****
static int ROWS = 0;
static int COLS = 0;
static boolean[] visited = null;
The two implementations of the function of interest are quite similar. The first one uses a set of three global variables. We need to populate the number of `ROWS` and `COLS` in the `board` and a boolean[] `visited` that is used to track when a cell in the `board` has been visited and used as part of the `word`. Perhaps I should have renamed the `visited` array `used`.
/**
* Given an m x n grid of characters board and a string word,
* return true if word exists in the grid.
*
* Execution: O(n * m) - Space O(n * m)
*
* Runtime: 82 ms, faster than 92.82% of Java online submissions.
* Memory Usage: 37.2 MB, less than 61.42% of Java online submissions.
*
* 80 / 80 test cases passed.
* Status: Accepted
* Runtime: 89 ms
* Memory Usage: 37 MB
*/
static boolean exist0(char[][] board, String word) {
// **** initialization ****
ROWS = board.length;
COLS = board[0].length;
// **** loop until word is found or all cells have been tried ****
for (int row = 0; row < ROWS; row++) {
for (int col = 0; col < COLS; col++) {
// **** search for word starting at this cell ****
if (word.charAt(0) == board[row][col]) {
// **** clear visited matrix ****
visited = new boolean[ROWS * COLS];
// **** depth first search ****
if (dfs0(board, row, col, word, 0)) return true;
}
}
}
// **** word not found ****
return false;
}
We start the first implementation of the function of interest initializing the two global variables `ROWS` and `COLS`.
Since we need to check if the first letter in the word is in each cell in the `board` we have a nested set of two loops. The first traverses the rows and the second the columns in each row.
Before we start a depth first search we check if the current cell in the `board` matches the first character in the `word`. If it does we clear the `visited` array and then call a depth first search for the characters in the `word`. If we found all characters in the `word` we return `true`; otherwise we keep looking for the next cell in the `board` that contains the first letter in `word`.
If we traverse all the cells in the board and the `word` is not found, we return `false`.
/**
* DFS recursive call.
* Makes use of visited boolean[][].
*/
static boolean dfs0(char[][] board, int row, int col, String word, int ndx) {
// **** check if we found the word ****
if (ndx >= word.length()) return true;
// **** determine if this cell has already been visited ****
if (visited[(row * COLS) + col] == true) return false;
// **** get current character from the word (for ease of use) ****
char c = word.charAt(ndx);
// **** current word character in this cell ****
if (c == board[row][col]) {
// **** flag that this cell is being visited ****
visited[(row * COLS) + col] = true;
// **** determine if the word has been found ****
if (ndx == (word.length() - 1)) return true;
// **** search right ****
if (col < (COLS - 1))
if (dfs0(board, row, col + 1, word, ndx + 1)) return true;
// **** search down ****
if (row < (ROWS - 1))
if (dfs0(board, row + 1, col, word, ndx + 1)) return true;
// **** search left ****
if (col > 0)
if (dfs0(board, row, col - 1, word, ndx + 1)) return true;
// **** search up ****
if (row > 0)
if (dfs0(board, row - 1, col, word, ndx + 1)) return true;
// **** flag that this cell was not visited ****
visited[(row * COLS) + col] = false;
}
// **** word not found ****
return false;
}
This function implements the depth first search algorithm. This is a recursive call.
The first two lines implement the end condition. Please look at the comments before each set of statements.
We get the character of interest from the `word` using the `ndx` argument.
We flag the current character in the `board` as visited.
We then check if the `ndx` reached the length of the `word`. If so, we are done and have found the `word` in the `board`.
We then look for the next character in the `word` right, down, left and up of the current cell by calling recursively the `dfs` function.
If the `word` is found the function returns `true`. If the `word` is not found we flag the current cell in the `board` as not visited so we can make use of it.
Finally if the search in all four directions did not find the `word`, we return `false`.
/**
* Given an m x n grid of characters board and a string word,
* return true if word exists in the grid.
*
* Execution: O(n * m) - Space: O(n * m)
*
* Runtime: 89 ms, faster than 88.20% of Java online submissions.
* Memory Usage: 37 MB, less than 81.90% of Java online submissions.
*
* 80 / 80 test cases passed.
* Status: Accepted
* Runtime: 89 ms
* Memory Usage: 37 MB
*/
static public boolean exist(char[][] board, String word) {
// **** loop once per row ****
for (int r = 0; r < board.length; r++) {
// **** loop once per column ****
for (int c = 0; c < board[0].length; c++) {
// **** search for word (if needed) ****
// if (word.charAt(0) == board[r])
if (dfs(board, r, c, word, 0)) return true;
}
}
// **** word not found ****
return false;
}
This is the second implementation of the function of interest. Please note that the approach is quite similar. The main difference is that we will not use global variables or the `visited` array.
Note that I commented out the check if the character at the current cell in the `board` matches the first character in the `word`. It seems that without such a check the code runs a couple milliseconds faster. Go figure.
/**
* DFS recursive call.
* Does not make use of visited boolean[][].
*/
static public boolean dfs(char[][] board, int r, int c,String word, int ndx) {
// **** base case(s) ****
if (ndx == word.length())
return true;
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r] != word.charAt(ndx))
return false;
// **** replace character on board ****
char tmp = board[r];
board[r] = '*';
// **** search in all four directions ****
boolean found = dfs(board, r, c + 1, word, ndx + 1) ||
dfs(board, r + 1, c, word, ndx + 1) ||
dfs(board, r, c - 1, word, ndx + 1) ||
dfs(board, r - 1, c, word, ndx + 1);
// **** restore character on board ****
board[r] = tmp;
// **** word found or not ****
return found;
}
This is a recursive function. We start by checking if the base conditions are met. In the first case the `word` was found in the `board`. In the second condition the indices for the current cell in the `board` are out of range, we were not able to find a match between the contents of the current cell, or the character in the `word` at the specified `ndx`.
Instead of using the `visited` array we replace the current cell character by a `*`. Since the contents of the string `word` may only contain lower or uppercase characters, `*` will not be selected.
We then perform a recursive call in the four directions from the current cell in the `board`.
After the calls return we restore the contents of the current cell in the `board`.
The contents of the `found` variable are returned to the caller.
/**
* Generate a string representation of the specified matrix.
* Auxiliary function.
* !!! NOT PART OF THE SOLUTION !!!
*/
static private String displayBoard(char[][] matrix) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** traverse the matrix ****
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
sb.append(matrix[r]);
if (c < matrix[0].length - 1) sb.append(", ");
else if (r < matrix.length - 1) sb.append('\n');
}
}
// **** return string with matrix contents ****
return sb.toString();
}
This is an auxiliary function that I used while developing the solutions. It seems that I did not leave the calls commented out but removed them from the code. I decided to leave the function in case I want to return to this problem in the future in order to see if I can improve on the execution time of the function of interest.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named WordSearch.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John