LeetCode 79. Word Search

发表于 | 0 comments | 阅读次数

这篇文章是 LeetCode 79. Word Search.md 的分析与解法。

问题描述

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

Given board =

1
2
3
4
5
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = ABCCED, -> returns true,

word = SEE, -> returns true,

word = ABCB, -> returns false.

这道题的意思就是在给定的字母板上寻找给定的单词，规则是从一个字母开始垂直或者水平方向上开始寻找，同一个位置的字母只能在路径上经过一次。

问题分析

这个问题首先能想到的方法就是暴力搜索，从字母板的(0, 0)位置开始搜索，到(n, n)位置结束。如果在搜索的过程中找到了给定的单词就直接返回。

以下图为例，假设我们要搜索的单词是『BED』，搜索顺序为『上下左右』：

搜索过程如下：

  1. 从(0, 0)位置的 A 开始搜索，A 与给定单词的[0]位置的字母不匹配，到(1, 0)位置；
  2. (1, 0)位置的 B 与给定单词的[0]位置的字母相同，按照 B 的上下左右的方向依次搜索，已经经过的位置不再搜索；
  3. 搜索至(1,1)位置的 E，与给定单词的[1]的字母相同，按照 E 的上下左右的方向依次搜索，已经经过的位置不再搜索；
  4. 直到搜索到 D，完成 BED 的搜索，返回。

代码实现

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
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0 || word.length() == 0 ){
            return false;
        }
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[i].size(); j++){
                if(search(board, word, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    bool search(vector<vector<char>>& board, string word, int x, int y, int pos){
        if(pos == word.length()){
            return true;
        }
        if(x < 0 || y < 0 || y >= board[x].size() || x >= board.size()){
            return false;
        }
        if(board[x][y] != word[pos]){
            return false;
        }
        char temp = board[x][y];
        board[x][y] = '*';

        bool result = search(board, word, x-1, y, pos+1)
        || search(board, word, x+1, y, pos+1)
        || search(board, word, x, y+1, pos+1)
        || search(board, word, x, y-1, pos+1);

        board[x][y] = temp;

        return result;
    }
};

本文的完整代码详见我的 GitHub

本文的版权归作者 罗远航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！