JAVA练习333- 单词搜索

题目概览

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

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

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board和word仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在board更大的情况下可以更快解决问题？

来源：79. 单词搜索 - 力扣（LeetCode）

解题分析

方法：回溯

我们令当前位置为 i, j，word 的当前索引为 index，那么：

  1. 当 i 或 j 越界时，返回 false
  2. 当 board[i][j] != word[index] 时，无法往下走，返回 false
  3. 当 board[i][j] == word[index] 时，index++，若此时 index == word 长度，返回 true，否则 将当前元素置空，然后朝着四个方向继续遍历，遍历完成后，回溯当前元素和 index

时间复杂度：O(mnx3^L) (其中 m,n 为网格的长度与宽度，L 为字符串 word 的长度)
空间复杂度：O(mn)

class Solution { public static int[][] directs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; 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 (backTracking(i, j, board, word, 0)) { return true; } } } return false; } public boolean backTracking(int i, int j, char[][] board, String word, int wordIndex) { if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(wordIndex)) { return false; } char temp = board[i][j]; wordIndex++; if (wordIndex == word.length()) { return true; } board[i][j] = '!'; for (int[] direct: directs) { if (backTracking(i + direct[0], j + direct[1], board, word, wordIndex)) { return true; } } wordIndex--; board[i][j] = temp; return false; } }