题目描述

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

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

题目分析

DFS，每层对应单词中的一个下标，使用visited数组标记哪个位置访问过

Java

private int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private boolean exist = false;

public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            dfs(board, new boolean[m][n], i, j, word, 0);
            if (exist) {
                return true;
            }
        }
    }
    return false;
}

private void dfs(char[][] board, boolean[][] visited, int i, int j, String word, int index) {
    int m = board.length;
    int n = board[0].length;
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index) || exist) {
        return;
    }
    if (index == word.length() - 1) {
        exist = true;
        return;
    }
    visited[i][j] = true;
    for (int[] dir : directions) {
        int newI = i + dir[0];
        int newJ = j + dir[1];
        dfs(board, visited, newI, newJ, word, index + 1);
    }
    visited[i][j] = false;
}

Kotlin

private val directions = arrayOf(intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1))
private var exist = false

fun exist(board: Array<CharArray>, word: String): Boolean {
    for (i in board.indices) {
        for (j in board[0].indices) {
            dfs(board, word, i, j, 0, Array(board.size) { BooleanArray(board[0].size) })
            if (exist) {
                return true
            }
        }
    }
    return false
}

private fun dfs(board: Array<CharArray>, word: String, i: Int, j: Int, index: Int, visited: Array<BooleanArray>) {
    if (i !in board.indices || j !in board[0].indices || board[i][j] != word[index] || visited[i][j] || exist) {
        return
    }
    if (index == word.length - 1) {
        exist = true
        return
    }
    visited[i][j] = true
    for (dir in directions) {
        dfs(board, word, i + dir[0], j + dir[1], index + 1, visited)
    }
    visited[i][j] = false
}