Reference: Problem I & Problem II Difficulty: Medium

Problem I
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" , return true .Given word = "SEE" , return true .Given word = "ABCB" , return false .board = [['A' ]] Given word = "A" , return true .board = [] or word = null return false .

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

Analysis Backtracking Consider how to write accept and reject base cases.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public boolean exist (char [][] board, String word) { if (word == null || word.length() == 0 || board == null || board.length == 0 ) { return false ; } int m = board.length; int n = board[0 ].length; boolean [][] visit = new boolean [m][n]; for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { if (backtracking(0 , i, j, board, word, visit)) return true ; } } return false ; } int [][] direction = { {-1 , 0 }, {1 , 0 }, {0 , -1 }, {0 , 1 } };private boolean backtracking (int pos, int i, int j, char [][] board, String word, boolean [][] visit) { if (pos == word.length() || word.charAt(pos) != board[i][j]) { return false ; } if (pos == word.length() - 1 ) { return true ; } visit[i][j] = true ; 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)) { return true ; } } } visit[i][j] = false ; return false ; }

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

Problem II Marked

Use `Trie`

.

https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)