首页 > 代码库 > 【LeetCode】Word Search

【LeetCode】Word Search

2024-07-05 18:54:58   217人阅读

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 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 

这题很显然需要DFS，而且递归在leetcode里基本上是TLE的，所以以下就是非递归的DFS。

核心思想如下：

用栈记录当前搜索的路径。

栈存放的节点包括4个成员：x,y坐标，word中的index，已遍历方向dir。

注意dir是非常重要的，用来记录已遍历过的方向（按照上下左右的顺序），不然的话就会出现无限循环的同一节点进栈出栈。

进栈之后的节点置为‘*‘，以免同一节点多次进栈。

出栈之后的节点恢复为word[index]。

其余DFS细节不赘述了，看代码就行。

 

class Solution {
public:
    struct grid
    {
        int x;
        int y;
        int index;    //在word中的index
        int dir;    //记录已遍历方向，用于回溯 0-无，1-上，2-下，3-左，4-右
    };

    bool exist(vector<vector<char> > &board, string word) 
    {
        stack<grid> stk;
        if(word.size() == 0)
            return true;
        int row = board.size();
        int col;

        for(int i = 0; i < row; i ++)
        {
            col = board[i].size();
            for(int j = 0; j < col; j ++)
            {
                if(board[i][j] == word[0])
                {
                    grid g;
                    g.x = i;
                    g.y = j;
                    g.index = 0;
                    g.dir = 0;
                    stk.push(g);
                    board[i][j] = ‘*‘;
                }
                while(!stk.empty())
                {
                    int x = stk.top().x;
                    int y = stk.top().y;
                    int index = stk.top().index;
                    int dir = stk.top().dir;
                    if(index == word.size()-1)
                    {
                        while(!stk.empty())
                        {
                            int x = stk.top().x;
                            int y = stk.top().y;
                            int index = stk.top().index;
                            int dir = stk.top().dir;
                            board[x][y] = word[index];
                            stk.pop();
                        }
                        return true;
                    }
                    if(x-1>=0 && board[x-1][y] == word[index+1] && dir == 0)
                    {
                        stk.top().dir = 1;
                        grid g;
                        g.x = x-1;
                        g.y = y;
                        g.index = index+1;
                        g.dir = 0;
                        stk.push(g);
                        board[x-1][y] = ‘*‘;
                    }
                    else if(x+1<row && board[x+1][y] == word[index+1] && dir <= 1)
                    {
                        stk.top().dir = 2;
                        grid g;
                        g.x = x+1;
                        g.y = y;
                        g.index = index+1;
                        g.dir = 0;
                        stk.push(g);
                        board[x+1][y] = ‘*‘;
                    }
                    else if(y-1>=0 && board[x][y-1] == word[index+1] && dir <= 2)
                    {
                        stk.top().dir = 3;
                        grid g;
                        g.x = x;
                        g.y = y-1;
                        g.index = index+1;
                        g.dir = 0;
                        stk.push(g);
                        board[x][y-1] = ‘*‘;
                    }
                    else if(y+1<board[x].size() && board[x][y+1] == word[index+1] && dir <= 3)
                    {
                        stk.top().dir = 4;
                        grid g;
                        g.x = x;
                        g.y = y+1;
                        g.index = index+1;
                        g.dir = 0;
                        stk.push(g);
                        board[x][y+1] = ‘*‘;
                    }
                    else
                    {
                        int x = stk.top().x;
                        int y = stk.top().y;
                        int index = stk.top().index;
                        board[x][y] = word[index];
                        stk.pop();
                    }
                }
                
            }
        }
        return false;
    }
};


联系
我们