题目描述

原题链接

给定一个 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 更大的情况下可以更快解决问题？

个人解法

Javascript

回溯

/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */
// @lc code=start
const dfs = function (board, i, j, target, m, n, res) {
  if (!target.length) {
    return true;
  }
  let str = target[0];
  const up = i > 0 ? board[i - 1][j] : null;
  const down = i < m - 1 ? board[i + 1][j] : null;
  const left = j > 0 ? board[i][j - 1] : null;
  const right = j < n - 1 ? board[i][j + 1] : null;
  let flag = false;
  if (res.indexOf(`${i - 1},${j}`) === -1 && up === str) {
    flag = dfs(board, i - 1, j, target.substring(1), m, n, [...res, `${i - 1},${j}`]) || flag;
    if (flag) {
      return true;
    }
  }
  if (res.indexOf(`${i + 1},${j}`) === -1 && down === str) {
    flag = dfs(board, i + 1, j, target.substring(1), m, n, [...res, `${i + 1},${j}`]) || flag;
    if (flag) {
      return true;
    }
  }
  if (res.indexOf(`${i},${j - 1}`) === -1 && left === str) {
    flag = dfs(board, i, j - 1, target.substring(1), m, n, [...res, `${i},${j - 1}`]) || flag;
    if (flag) {
      return true;
    }
  }
  if (res.indexOf(`${i},${j + 1}`) === -1 && right === str) {
    flag = dfs(board, i, j + 1, target.substring(1), m, n, [...res, `${i},${j + 1}`]) || flag;
    if (flag) {
      return true;
    }
  }
  return flag;
}
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length;
  const n = board[0].length;
  const res = [];
  const result = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === word[0]) {
        res.push([i, j]);
      }
    }
  }
  const len = res.length;
  if (len === 0) {
    return false;
  }
  for (let i = 0; i < len; i++) {
    res[i] = dfs(board, res[i][0], res[i][1], word.substring(1), m, n, [`${res[i][0]},${res[i][1]}`]);
    if (res[i]) {
      return true;
    }
  }
  return res.indexOf(true) > -1;
};
// @lc code=end

Java

回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        int w=board[0].length,h=board.length;
        boolean[][] flag=new boolean[h][w];
        for (int i=0;i<h;i++){
            for (int j=0;j<w;j++){
                boolean result=check(board,word,flag,i,j,0);
                if (result==true){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean check(char[][] board,String word,boolean[][] flag,int i,int j,int k){
        //如果当前字符和位置k的目标字符不相等，直接返回false
        if (board[i][j]!=word.charAt(k)){
            return false;
        //如果最后一位字符对应字符也找到了，说明字符串存在，返回true
        }else if (k==word.length()-1){
            return true;
        }
        //当前字符和位置k目标字符对应，寻找下一个字符，标记当前字符已访问
        flag[i][j]=true;
        boolean result=false;
        //上下左右
        int[][] nums=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] n:nums){
            int newI=i+n[0],newJ=j+n[1];
            //判断有没有越界
            if (newI>=0&&newJ>=0&&newI< board.length&&newJ<board[0].length){
                if (flag[newI][newJ]==false){
                    boolean f=check(board, word, flag, newI, newJ, k+1);
                    if (f==true){
                        result=true;
                        break;
                    }
                }
            }
        }
        //复原当前字符状态，不阻碍下一次寻找
        flag[i][j]=false;
        return result;
    }
}

其他解法

Java

Javascript

DFS优化

/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */
// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const h = board.length, w = board[0].length;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  const visited = new Array(h);
  for (let i = 0; i < visited.length; ++i) {
    visited[i] = new Array(w).fill(false);
  }
  const check = (i, j, s, k) => {
    if (board[i][j] != s.charAt(k)) {
      return false;
    } else if (k == s.length - 1) {
      return true;
    }
    visited[i][j] = true;
    let result = false;
    for (const [dx, dy] of directions) {
      let newi = i + dx, newj = j + dy;
      if (newi >= 0 && newi < h && newj >= 0 && newj < w) {
        if (!visited[newi][newj]) {
          const flag = check(newi, newj, s, k + 1);
          if (flag) {
            result = true;
            break;
          }
        }
      }
    }
    visited[i][j] = false;
    return result;
  }
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      const flag = check(i, j, word, 0);
      if (flag) {
        return true;
      }
    }
  }
  return false;
};
// @lc code=end