首页 > 代码库 > 【Leetcode】79. Word Search
【Leetcode】79. Word Search
思路:
遍历矩阵,结合dfs解即可。
#include <iostream> #include <vector> using namespace std; class Solution { public: Solution() {} bool exist(vector<vector<char>>& board, string word) { //初始化都没有被访问过 this->rowCount = board.size(); if (rowCount == 0) { return false; } this->colCount = board[0].size(); for (int i = 0; i < rowCount; i++) { vector<int> v(colCount, 0); visit.push_back(v); } this->word = word; this->board = board; for (int i = 0; i < rowCount; i++){ for (int j = 0; j< colCount; j++) { if (board[i][j] == word[0] && dfs(i, j, 0)) { return true; } } } return false; } /** *@param row 当前字符所在行 *@param col 当前字符所在列 *@param index word当前被扫描的位置 */ bool dfs(int row, int col, int index) { if (index == word.size() - 1) { return true; } //当前位置标志为被访问 visit[row][col] = 1; //up if (row - 1 >= 0 && !visit[row - 1][col] && board[row - 1][col] == word[index + 1] ) { if (dfs(row - 1, col, index + 1)) { return true; } } //down if (row + 1 < this->rowCount && !visit[row + 1][col] && board[row + 1][col] == word[index + 1]) { if (dfs(row + 1, col, index + 1)) { return true; } } //left if (col - 1 >= 0 && !visit[row][col - 1] && board[row][col - 1] == word[index + 1]) { if (dfs(row, col - 1, index + 1)) { return true; } } //right if (col + 1 < this->colCount && !visit[row][col + 1] && board[row][col + 1] == word[index + 1]) { if (dfs(row, col + 1, index + 1)) { return true; } } //不满足,置为0 visit[row][col] = 0; return false; } private: vector<vector<char>> board; string word; vector<vector<int>> visit; int rowCount; int colCount; }; int main(int argc, char *argv[]) { vector<vector<char>> board = { {‘a‘,‘b‘}}; Solution s; string word = "ba"; bool ret = s.exist(board, word); cout<<ret<<endl; return 0; }
【Leetcode】79. Word Search
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。