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_;
};

http://xzh.i3geek.com