Problem: 79.单词搜索
基本思路
典型的棋盘探索问题,使用回溯(DFS)算法解决。 可以使用位运算标记使用的过的棋盘位置。
.... /** 标记 */ board[i][j] |= 0x100; .... /** 去标记 */ board[i][j] ^= 0x100;
代码
Java
class Solution { public boolean exist(char[][] board, String word) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfs(board, word, i, j, 0)) { return true; } } } return false; } boolean dfs(char[][] board, String word, int i, int j, int length) { if (board[i][j] != word.charAt(length)) { return false; } else if (word.length() == length + 1) { return true; } board[i][j] |= 0x100; if ((i > 0 && (board[i - 1][j] & 0x100) == 0 && dfs(board, word, i - 1, j, length + 1)) || (j > 0 && (board[i][j - 1] & 0x100) == 0 && dfs(board, word, i, j - 1, length + 1)) || (i < board.length - 1 && (board[i + 1][j] & 0x100) == 0 && dfs(board, word, i + 1, j, length + 1)) || (j < board[0].length - 1 && (board[i][j + 1] & 0x100) == 0 && dfs(board, word, i, j + 1, length + 1))) { return true; } board[i][j] ^= 0x100; return false; } }
复杂度分析
- 时间复杂度:。 为网格的长度与宽度, 为字符串 word 的长度。网格的每个位置探索 次,总计 次;每次探索除了在 word 的第一个字符位置需要进行 次探索,其余位置仅探索 次。
- 空间复杂度:。栈的深度最大为字符串 word 的长度。