Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Word Search

Leetcode algorithms 第 79 题:Word Search。

题目

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 =
word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

解答

在一个二维数组中寻找一个单词,每次可以向相邻位置移动。遍历整个矩阵,找到跟首字母匹配的位置,然后从该位置开始进行深度优先搜索遍历,看能否找到给定的单词。

搜索时每次朝四个方向走动,如果没有越界、没有访问并且字母匹配时,可以走到该位置并进行下一次搜索,直到找到答案为止。

具体代码如下:

class Solution {
public:
    int n, m;
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0}; //四个方向移动的增量
    
    bool dfs(int x, int y, int id, vector<vector<bool>> &vs, vector<vector<char> > &board, string &word)
    { //当前的行,列,单词下标,已访问的数组,二维数组,单词
        if (id == word.size()) return true;  //已找到
        
        for (int i = 0; i < 4; ++i)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && !vs[tx][ty] && board[tx][ty] == word[id])
            { //未超出边界,未访问,且字母匹配
                vs[tx][ty] = true;
                if (dfs(tx, ty, id+1, vs, board, word)) return true;
                vs[tx][ty] = false; //回溯
            }
        }
        return false;
    }
    bool exist(vector<vector<char> > &board, string word) {
        if (word.empty()) return true;
        if (board.empty()) return false;
        n = board.size(), m = board[0].size();
        
        vector<vector<bool>> vs(n, vector<bool>(m, false));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                if (board[i][j] == word[0]) //首字母匹配
                {
                    vs[i][j] = true;
                    if (dfs(i, j, 1, vs, board, word)) return true;
                    vs[i][j] = false;
                }
            }
        return false;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论