给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false
提示:
board 和 word 仅由大小写英文字母组成
递归的关键点
那么,哪些情况说明这是一个错的点:
class Solution { public boolean exist(char[][] board, String word) { if (board == null || board.length == 0) { return false; } boolean[][] visited = new boolean[board.length][board[0].length]; char[] chars = word.toCharArray(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (existHelper(board, visited, chars, i, j, 0)) { return true; } } } return false; } private boolean existHelper(char[][] board, boolean[][] visited, char[] chars, int row, int column, int index) { if (index == chars.length) { return true; } int[][] direction = new int[][]{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; if (row >= 0 && row < board.length && column >= 0 && column < board[0].length && board[row][column] == chars[index] && !visited[row][column]) { visited[row][column] = true; for (int[] dir : direction) { int newX = row + dir[0]; int newY = column + dir[1]; if (existHelper(board, visited, chars, newX, newY, index + 1)) { return true; } } visited[row][column] = false; } return false; } }
时间复杂度:O(M*N * 3^L)
空间复杂度:O(M*N)
思路同上
func exist(board [][]byte, word string) bool { m, n := len(board), len(board[0]) used := make([][]bool, m) for i := 0; i < m; i++ { used[i] = make([]bool, n) } var canFind func(r, c, i int) bool canFind = func(r, c, i int) bool { if i == len(word) { return true } if r < 0 || r >= m || c < 0 || c >= n { return false } if used[r][c] || board[r][c] != word[i] { return false } used[r][c] = true canFindRest := canFind(r+1, c, i+1) || canFind(r-1, c, i+1) || canFind(r, c+1, i+1) || canFind(r, c-1, i+1) if canFindRest { return true } else { used[r][c] = false return false } } for i := 0; i < m; i++ { for j := 0; j < n; j++ { if board[i][j] == word[0] && canFind(i, j, 0) { return true } } } return false }
时间复杂度:O(M*N * 3^L)
空间复杂度:O(M*N)