0079._Search_Word

发表于 分类于 ， ，

0079. Word Seach

难度: Medium

刷题内容

原题连接

内容描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

 board =
 [
   ['A','B','C','E'],
   ['S','F','C','S'],
   ['A','D','E','E']
 ]

 给定 word = "ABCCED", 返回 true.
 给定 word = "SEE", 返回 true.
 给定 word = "ABCB", 返回 false.

解题方案

思路
**- 时间复杂度: O(?)**- 空间复杂度: O(1)**

这个时间复杂度我不知道如何分析

思路是深度优先搜索

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    let height = board.length;
    let width = board[0].length;
    let result = false;
    for(let x = 0; x < height; x++) {
        for(let y = 0; y < width; y++) {
            if (board[x][y] === word[0]) {
                result = result || searchDFS(board, [ x, y ], shiftWord(word), [[x,y]])
            }
        }
    }
    return result;
};

var searchDFS = function (board, [x,y], word, useList = []) {
    const list = [...useList];
    let result = false;
    if(!word || !word.length) {
        return true;
    }

    // 上
    if(x > 0 && board[x-1][y] === word[0] && !positionInList([x-1,y], list)) {
        const l = [...list]
        l.push([x-1, y]);
        result = result || searchDFS(board, [x-1,y], shiftWord(word), l);
    }

    // 下
    if (x < board.length-1 && board[x+1][y] === word[0] && !positionInList([x+1,y], list)) {
        const l  = [...list]
        l.push([x+1, y]);
        result = result || searchDFS(board, [x+1,y], shiftWord(word), l);
    }

    // 左
    if (y > 0 && board[x][y-1] === word[0] && !positionInList([x,y-1], list)) {
        const l = [...list]
        l.push([x, y-1]);
        result = result || searchDFS(board, [x,y-1], shiftWord(word), l);
    }

    // 右
    if (y < board[0].length-1 && board[x][y+1] === word[0] && !positionInList([x,y+1], list)) {
        const l = [...list]
        l.push([x, y+1]);
        result = result || searchDFS(board, [x,y+1], shiftWord(word), l);
    }

    return result;
}

var positionInList = function ([x, y], list = []) {
    return list.some(([oX, oY]) => (oX === x && oY === y))
}

var shiftWord = function (word) {
    return Array.prototype.slice.call(word, 1).join('')
}