[LeetCode] 79. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

单词搜索。

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是回溯。需要写一个helper函数进行递归，同时也需要一个visited二维数组记录是否visited过某个点。

第七行当word的第一个字母在board中被找到，即可开始做回溯，回溯是往当前这个坐标的上下左右四个方向接着找下一个字母是否存在
helper函数里面几个边界条件是
- 如果扫描的时候已经到达word的长度，则return true
- 如果扫描的时候超过了board的边界，则return false
- 如果有字母已经被扫描过，则return false - 这是为了防止走回头路
- 如果word当前字母不等于board当前被扫描的字母，则return false
- 接着往四个方向回溯做，如果这四个方向有一个方向能扫描到word结尾则整个函数可以返回true，否则需要回溯回到当前坐标board[row][col]并把它标记成unvisited

时间 - ?

空间 - ?

Java实现

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

flood fill题型总结

LeetCode 题目总结