Leetcode.79.Word Search

题目

给定一个二维数组和一个字符串, 判断能否从二维数组中找到该字符串. 找寻路径不能重复.

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

思路

递归. 从第一个元素开始查询, 然后下一个元素在上下左右去遍历. 需要判断查询路径是否重复.

bool recrutionExtist(vector<vector<char>>& board,vector<char> &words,vector<char> &temp,int i,int j,int index, set<pair<int,int>> &cache) {

  int rowCount = board.size();
  int colCount = board[0].size();
  if (i >= rowCount || i < 0 || j >= colCount || j < 0) {
      return temp.size() == words.size();
  }

  if (temp.size() == words.size()) {
      return true;
  }

  if (board[i][j] == words[index] && cache.find(make_pair(i,j)) == cache.end()) { 
      temp.push_back(board[i][j]);
      cache.insert(make_pair(i,j));
      if (recrutionExtist(board, words, temp, i-1, j, index+1, cache)) {
          return true;
      }
      if (recrutionExtist(board, words, temp, i+1, j, index+1, cache)) {
          return true;
      }
      if (recrutionExtist(board, words, temp, i, j-1, index+1, cache)) {
          return true;
      }
      if (recrutionExtist(board, words, temp, i, j+1, index+1, cache)) {
          return true;
      }
      temp.pop_back();
      cache.erase(make_pair(i,j));
  }
  return false;
}

bool exist(vector<vector<char>>& board, string word) {
  int rowCount = board.size();
  if (rowCount == 0) {
      return false;
  }
  int colCount = board[0].size();

  vector<char> words;
  words.resize(word.size());
  words.assign(word.begin(), word.end());

  for (int i = 0; i < rowCount; i++) {
      for (int j = 0; j < colCount; j++) {
          vector<char> temp;
          set<pair<int,int>> cache;
          if(recrutionExtist(board, words, temp, i, j, 0, cache)) {
              return true;
          }
      }
  }   

  return false;
}

总结

递归的思想, 主要是理清楚递归的思路.