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.lengthn board[i].length1 m, n 61 word.length 15board和word仅由大小写英文字母组成进阶你可以使用搜索剪枝的技术来优化解决方案使其在board更大的情况下可以更快解决问题来源79. 单词搜索 - 力扣LeetCode解题分析方法回溯我们令当前位置为 i, jword 的当前索引为 index那么当 i 或 j 越界时返回 false当 board[i][j] ! word[index] 时无法往下走返回 false当 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; } }