Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", returntrue. Given word = "SEE", returntrue. Given word = "ABCB", returnfalse.

board = [['A']] Given word = "A", returntrue.

board = [] or word = null returnfalse.

Follow up: Reduce space complexity to $O(1)$.

Analysis

Backtracking

Consider how to write accept and reject base cases.

publicbooleanexist(char[][] board, String word){ if (word == null || word.length() == 0 || board == null || board.length == 0) { returnfalse; } int m = board.length; int n = board[0].length; boolean[][] visit = newboolean[m][n]; // since each cell is visited once for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (backtracking(0, i, j, board, word, visit)) returntrue; } } returnfalse; }

privatebooleanbacktracking(int pos, int i, int j, char[][] board, String word, boolean[][] visit){ // reject - character not equal if (pos == word.length() || word.charAt(pos) != board[i][j]) { returnfalse; } // accept if (pos == word.length() - 1) { returntrue; } // visit visit[i][j] = true; // check its neighbors int m = board.length; int n = board[0].length; for (int[] dir : direction) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y]) { if (backtracking(pos + 1, x, y, board, word, visit)) { returntrue; } } } visit[i][j] = false; returnfalse; }

Can be optimized by setting board[i][j] ^= 256 and check if board[x][y] is less than 256. So we don’t need extra space.

Time: $O(MN \times 4^K)$ where $K$ is the length of the string. Space: $O(MN)$