79.单词搜索.md

79. 单词搜索

url

题目

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

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

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

方法

code

js

let exist = (board, word) => {
    if (board === null || board.length === 0 || board[0].length === 0)
        return false;
    let next = [[1,0],[-1,0],[0,1],[0,-1]];
    let m = board.length, n = board[0].length;
    let marked = Array(m).fill(false).map(() => Array(n).fill(false));
    let dfs = (word, pathLen, i, j) => {
        if (pathLen === word.length)
            return true;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[pathLen] || marked[i][j])
            return false;
        marked[i][j] = true;
        for (let d of next) {
            if (dfs(word, pathLen + 1, i + d[0], j + d[1]))
                return true
        }
        marked[i][j] = false;
        return false
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(word, 0, i, j))
                return true
        }
    }
    return false
}

go

func exist(board [][]byte, word string) bool {
	next := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
	m, n := len(board), len(board[0])
	marked := make([][]bool, m)
	for i := range marked {
		marked[i] = make([]bool, n)
	}
	var dfs func(board [][]byte, word string, pathLen, i, j int) bool
	dfs = func(board [][]byte, word string, pathLen, i, j int) bool {
		if pathLen == len(word) {
			 return true
		}
		if i<0 || i>=m || j<0 || j>=n || board[i][j] != word[pathLen] || marked[i][j] {
			return false
		}
		marked[i][j] = true
		for _, d := range next {
			if dfs(board, word, pathLen+1, i+d[0], j+d[1]) {
				return true
			}
		}
		marked[i][j] = false
		return false
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(board, word, 0, i, j) {
				return true
			}
		}
	}
	return false
}

java

class Solution {
    private int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int m, n;
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return false;
        this.m = board.length;
        this.n = board[0].length;
        boolean[][] marked = new boolean[m][n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (dfs(board, word, marked, 0, i, j))
                    return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, boolean[][] marked, int pathLen, int i, int j){
        if (pathLen == word.length())
            return true;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(pathLen) || marked[i][j])
            return false;

        marked[i][j] = true;
        for (int[] n : next) {
            if (dfs(board, word, marked, pathLen +1, i + n[0], j + n[1]))
                return true;
        }
        marked[i][j] = false;
        return false;
    }
}