DFS word search through a matrix.
Time complexity = O(m * n * 4^k) where m and n is the size of the matrix and k is the length of word.
Explanation: We start the word search over all m * n nodes. For the word search we can move at most in 4 directions.
Space complexity = O(k), where k is the length of word (recursive space).
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (search(i, j, 0, word, board)) {
return true;
}
}
}
return false;
}
private boolean search(int i, int j, int index, String word, char[][] board) {
if (index == word.length()) {
return true;
}
if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1) {
return false;
}
if (word.charAt(index) != board[i][j]) { // 强剪枝
return false;
}
char cur = board[i][j];
board[i][j] = '#';
boolean found = search(i + 1, j, index + 1, word, board)
|| search(i - 1, j, index + 1, word, board)
|| search(i, j - 1, index + 1, word, board)
|| search(i, j + 1, index + 1, word, board);
board[i][j] = cur;
return found;
}
}