Leetcode79. Word Search单词搜索

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

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

示例:

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.

class Solution {

public:

    vector<vector<int> > visit;

    int len;

    int r;

    int c;

    int dx[4] = {1, -1, 0, 0};

    int dy[4] = {0, 0, 1, -1};

    bool exist(vector<vector<char> >& board, string word)

    {

        len = word.size();

        if(len == 0)

            return true;

        r = board.size();

        if(r == 0)

            return false;

        c = board[0].size();

        if(r * c < len)

            return false;

        for(int i = 0; i < r; i++)

        {

            for(int j = 0; j < c; j++)

            {

                visit.clear();

                visit = vector<vector<int> >(r, vector<int>(c, 0));

                if(board[i][j] == word[0])

                {

                    visit[i][j] = 1;

                    if(DFS(board, 1, word, i, j))

                    return true;

                }

            }

        }

        return false;

    }

        bool DFS(vector<vector<char> >& board, int pos, string cmp, int x, int y)

        {

            if(pos >= cmp.size())

                return true;

            for(int i = 0; i < 4; i++)

            {

                int xx = x + dx[i];

                int yy = y + dy[i];

                if(xx < 0 || xx >= r || yy < 0 || yy >= c)

                    continue;

                if(visit[xx][yy] == 1)

                    continue;

                if(board[xx][yy] != cmp[pos])

                    continue;

                visit[xx][yy] = 1;

                if(DFS(board, pos + 1, cmp, xx, yy))

                    return true;

                visit[xx][yy] = 0;

            }

            return false;

        }

};

巴特西

Leetcode79. Word Search单词搜索

最新文章

热门文章