79. Word Search

发表于 | 分类于

每日一题 2019 - 04 - 14

题目：

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.

Example:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

解法：

这个题要求判定在给定二维字符图中能否找到给定的字符串，最直观的思路就是对全图就行暴力搜索，当然搜索也要有一定技巧：

  • 从地图左上往右下搜索，对每一个格子的前后左右进行进一步搜索，只要有一个格子满足序列的要求，就继续顺着这个格子往后搜索
  • 需要注意，序列越界或者当前遍历的字符在地图上找不到，那就证明搜索错误，直接宣告本次搜索失败

代码：

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) {
        int length = board[0].size();
        int width = board.size() ;
        if (word.empty()) return true;
        if (board.empty() || board[0].empty()) return false;
        vector<vector<bool>> temp(width, vector<bool> (length,false));
        for(int i = 0 ;  i < width ; i ++)
        {
            for(int j = 0 ; j < length ; j ++)
            {
                if(word_search(board,word,0,i,j,temp))
                {
                    return true;
                }    
            }
        }
        return false ;
    }
    bool word_search(vector<vector<char>>& board,string word,int size,int i, int j,vector<vector<bool>> &now)
    {
        if( size == word.size())
        {
            return true ;
        }
        if( i < 0 || j < 0 || i == board.size() || j == board[0].size() || now[i][j] == true || word[size]!=board[i][j])
        {
            return false ;
        }
        now[i][j] = true ;
        bool res = word_search(board,word,size+1,i-1,j,now) ||
            word_search(board,word,size+1,i,j-1,now)||
            word_search(board,word,size+1,i+1,j,now)||
            word_search(board,word,size+1,i,j+1,now);
        now[i][j] = false;
        return res ;
    }
};
0%
undefined