Word Search（C++单词搜索）

淡淡的烟草味﹌ 2022-10-11 13:46 180阅读 0赞

（1）回溯

（2）返回时重置为未访问

class Solution {
    
    private:
        vector<vector<char>> d={
       {1,0},{-1,0},{0,1},{0,-1}};
        int ms,ns;
    public:
    
        bool helper(vector<vector<char>>& board,vector<vector<bool>> &vis,int i,int j,int len,string &word,int count) {
            count++;
            if(count==len) {
                return true;
            }
            vis[i][j]=true;
    
            for(int k=0;k<d.size();k++) {
                int x1=i+d[k][0];
                int y1=j+d[k][1];
    
                if(0<=x1 && x1<ms && 0<=y1 && y1<ns && vis[x1][y1]==false && board[x1][y1]==word[count]) {
                    if(helper(board,vis,x1,y1,len,word,count)) return true;
                }
            }
    
            vis[i][j]=false;
            return false;
        }
        bool exist(vector<vector<char>>& board, string word) {
            ms=board.size(),ns=board[0].size();
            int len=word.length();
            vector<vector<bool>> vis(ms,vector<bool>(ns,false));
    
            for(int i=0;i<ms;i++) {
                for(int j=0;j<ns;j++) {
                    if(board[i][j]==word[0]) {
                        if(helper(board,vis,i,j,len,word,0)) return true;
                    }
                }
            }
            return false;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 79. 单词搜索

79. 单词搜索给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

梦里梦外;/ 2024年03月31日 02:17/ 0 赞/ 92 阅读

相关 79. 单词搜索

> [https://leetcode-cn.com/problems/word-search/][https_leetcode-cn.com_problems_word-se

喜欢ヅ旅行/ 2022年12月05日 05:24/ 0 赞/ 199 阅读

相关 Word Search（C++单词搜索）

（1）回溯（2）返回时重置为未访问 class Solution { private: vector<vector<cha

淡淡的烟草味﹌/ 2022年10月11日 13:46/ 0 赞/ 181 阅读

相关 Word Search II（c++单词搜索 II）

（1）回溯+前缀树 class Trie { public: vector<Trie> v; bool isend;

向右看齐/ 2022年09月02日 04:16/ 0 赞/ 221 阅读

相关 leetcode 79. Word Search | 79. 单词搜索（回溯+DFS）

题目 [https://leetcode.com/problems/word-search/][https_leetcode.com_problems_word-sear

亦凉/ 2022年08月28日 09:58/ 0 赞/ 212 阅读

相关 leetcode 79. Word Search DFS 单词搜索 + 深度优先遍历

Given a 2D board and a word, find if the word exists in the grid. The word can be const

墨蓝/ 2022年06月08日 02:13/ 0 赞/ 259 阅读

相关 [Leetcode][python]Word Search/单词搜索

题目大意在一个二维矩阵中，每个元素都是一个字母，要判断目标字符串能否由该矩阵中的元素连接而成。所谓连接就是从矩阵中的某一个元素开始，向前后左右不断前进，但不允许再次经过

阳光穿透心脏的1/2处/ 2022年06月07日 13:35/ 0 赞/ 259 阅读

相关 LeetCode 单词搜索

要求：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那

淩亂°似流年/ 2022年05月17日 03:13/ 0 赞/ 206 阅读

相关 leetcode 单词搜索

> 给定一个二维网格和一个单词，找出该单词是否存在于网格中。 > 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一

傷城~/ 2021年11月02日 09:20/ 0 赞/ 369 阅读

相关 LeetCod ：79. Word Search 单词搜索

试题 Given a 2D board and a word, find if the word exists in the grid. The word can be

迈不过友情╰/ 2021年06月24日 16:11/ 0 赞/ 409 阅读