LeetCode: 79. Word Search

转载请注明, 原文地址:LeetCode: 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.

link:https://leetcode.com/problems/word-search/

要点

1.边界条件,dfs时候不可以越界
2.每个元素只能使用一次。简单方法是使用vector<vector>来标记对应的char,或者直接修改board节省内存(参考了Grandyang大佬的思路),效率也会高一点。

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        bottom_ = board.size() - 1;
        right_ = board[0].size() - 1;
        auto size = word.size() - 1;

        for (int i = 0; i <= bottom_; ++i) {
            for (int j = 0; j <= right_; ++j) {
                if (dfs(i, j, 0, size, board, word))
                    return true;
            }
        }
        return false;
    }

    bool dfs(int x, int y, int index,
        const size_t& size,
        vector<vector<char>>& board, string& word) {
        if (board[x][y] == word[index]) {
            board[x][y] = '.';
            if (index == size) {
                return true;
            }
            if (x > 0 && board[x-1][y]!= '.' 
                && dfs(x - 1, y, index + 1, size, board, word)) return true;
            if (y > 0 && board[x][y-1] != '.' 
                && dfs(x, y - 1, index + 1, size, board, word)) return true;
            if (x < bottom_ && board[x+1][y] != '.' 
                && dfs(x + 1, y, index + 1, size, board, word)) return true;
            if (y < right_ && board[x][y+1] != '.' 
                && dfs(x, y + 1, index + 1, size, board, word)) return true;

            board[x][y] = word[index];
        }
        return false;
    }

    int bottom_;
    int right_;
};

转载请注明:

转载自YuLai's Blog,原文地址:LeetCode: 79. Word Search

发表评论

发表评论

*

沙发空缺中,还不快抢~