LeetCodeDay54 —— 单词搜索★★

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.

示例

board =
  [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
  ]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

思路

1. 从每个字母开始，依次向上、下、左、右四个方向延续，如果满足则继续，不满足就返回。很典型的回溯算法。
2. 注意每次遍历的时候需要标记当前节点为已访问，否则会出现圈，造成死循环。

class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    if (board.empty() || board[0].empty()) return false;
    vector<vector<bool>> tag;
    vector<bool> tmp(board[0].size(), false);
    for (int i = 0; i < board.size(); ++i) {
      tag.push_back(tmp);
    }
    for (int i = 0; i < board.size(); ++i) {
      for (int j = 0; j < board[0].size(); ++j) {
        bool isFind = _exist(0, i, j, word, board, tag);
        if (isFind) return true;
      }
    }
    return false;
  }
  bool _exist(int k, int row, int col, string& word,
              vector<vector<char>>& board, vector<vector<bool>>& tag) {
    bool isFind = false;
    if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
      return isFind;
    }
    if (!tag[row][col] && board[row][col] == word[k]) {
      if (k == word.size() - 1) return true;
      tag[row][col] = true;
      isFind = _exist(k + 1, row - 1, col, word, board, tag) ||
               _exist(k + 1, row + 1, col, word, board, tag) ||
               _exist(k + 1, row, col - 1, word, board, tag) ||
               _exist(k + 1, row, col + 1, word, board, tag);
      tag[row][col] = false;
    }
    return isFind;
  }
};