`
cozilla
  • 浏览: 93896 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] 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.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 

 

同学们把leetcode刷了一遍又一遍~

 

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        int n = board.size();
        if (n == 0) return false;
        int m = board[0].size();
        set<pair<int,int> >s;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (check(board, word, i, j, 0, s) == true) return true;
            }
        }
        return false;
    }
    
    bool check(vector<vector<char> >&a, string& w, int x, int y, int cnt, set<pair<int,int> >&s) {
        if (cnt == w.size()) return true;
		if (x >= a.size() || x < 0 || y >= a[0].size() || y < 0) return false;
        if (s.count(make_pair(x,y)) > 0)return false;
        if (w[cnt] != a[x][y]) return false;
        s.insert(make_pair(x,y));
        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        for (int i = 0; i < 4; i++) {
            if (check(a, w, x+dx[i], y+dy[i], cnt+1, s) == true) return true;
        }
        s.erase(make_pair(x,y));
        return false;
    } 
};

 

分享到:
评论

相关推荐

    python-leetcode题解之079-Word-Search

    python python_leetcode题解之079_Word_Search

    c语言-leetcode题解之0079-word-search.zip

    LeetCode题号0079的题目是Word Search,即单词搜索。这个问题属于经典的回溯算法应用场景,具体要求是在一个二维的字符数组中查找是否存在某个给定的单词。这个问题不仅考验了编程者对回溯算法的理解和应用,还涉及...

    C语言-leetcode题解之79-word-search.c

    关于“C语言-leetcode题解之79-word-search.c”,这是一份针对leetcode在线编程题库中编号为79的题目“Word Search”的C语言解决方案。这道题属于回溯算法的经典应用,题目要求在一个二维的字符网格中寻找是否存在一...

    LeetCode最全代码

    318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...

    js-leetcode题解之79-word-search.js

    此外,"js-leetcode题解之79-word-search.js" 这个文件的标题和描述还提示我们,该文件可能是一段 JavaScript 语言编写的代码,用于解决 LeetCode 上编号为 79 的题目。文件的具体内容可能会包含题目描述、解题思路...

    LeetCode题解(java语言实现).pdf

    LeetCode题解(java语言实现) 本资源提供了LeetCode题解的Java语言实现,涵盖了多种算法和数据结构,包括数组、链表、树、图、动态规划、贪心算法等。该资源共包含71个LeetCode题解,涵盖了多个难度级别的题目,...

    _leetcode-python.pdf

    - Word Search: 给定一个m×n的二维字符网格board和一个单词(字符串)word,如果word存在于网格中,则返回true;否则,返回false。 - Minimum Window Substring: 给定两个字符串s和t,找出s中包含t所有字母的最小子...

    Leetcode题目+解析+思路+答案.pdf

    - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List)**: - **Linked List Cycle**:检测链表中的环。 - **Remove Duplicates from Sorted List**:从已排序的...

    LeetCode各公司题目合集

    - Word Search II:这是一个在二维网格中寻找单词的题目,它涉及到深度优先搜索(DFS)和字典树(Trie)的使用,适合考查候选人的数据结构掌握情况和字符串处理能力。 - Two Sum:这个经典的题目要求找出数组中两个...

    js-leetcode题解之127-word-ladder.js

    本文探讨的是leetcode中127号问题——Word Ladder(单词梯度)的JavaScript解法。 Word Ladder问题是一个经典的字符串转换问题,要求给定一个起始单词beginWord,一个结束单词endWord和一个单词列表wordList,我们...

    js-leetcode题解之139-word-break.js

    LeetCode题号139的这道“Word Break”题便是这样一个问题。该问题要求实现一个函数,该函数接收两个参数:一个字符串s和一个字符串数组wordDict作为字典,返回一个布尔值,表示是否可以将字符串s拆分为字典中的单词...

    算法刷题笔记leetcode/lintcode

    - Length of Last Word(最后一个单词的长度) - Count and Say(猜数字序列) - **Integer Array**(整型数组操作) - Remove Element(移除元素) - Zero Sum Subarray(连续子数组的最大和) - Subarray Sum...

    leetcode苹果-LeetCode_No.208_-:LeetCode_No.208_-

    leetcode 苹果 LeetCode_No.208_-实现 Trie (前缀树) 题目介绍 Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完...

    LeetCode:关于LeetCode.com和ACM的一些算法问题

    LeetCode一些 LeetCode 题目的进阶解法,追求极致效率。由于 LeetCode 已启用中文版域名 leetcode-... Word-Search-II题目: | 英文站源码:./problem-0212-Word-Search-II/标签:哈希表,双向链表难度:困难 / Hard

    leetcode不会-word-search:二维网格中的单词搜索

    leetcode 不会词搜索 给定一个 2D 板和一个单词,查找该单词是否存在于网格中。 单词可以由顺序相邻的单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能多次使用。 Example: ...

    leetcode寻找最近的-leetcode:leetcode题目

    search_word79.cpp。 链表基本操作要进行删除元素,那么在循环的过程中尽量使用前驱进行循环。提前校验head,head-&gt;next。new一个空头部。头插法pcur是空头后一位。 对于查找查找类的题目首先考虑二分查找,但是二分...

    hihocoder和leetcode-leetcode:leetcode

    hihocoder和leetcode leetcode 目录名 功能 Array 数组 Backtracking 回溯 Bit_Manipulation 位操作 Design 数据结构设计 ...单词搜索:word_search.cpp hihocoder String 文章重排:give_my_text_back.cpp

    python-leetcode面试题解之第208题实现前缀树-题解.zip

    2. `search(word)`: 检查前缀树中是否存在给定的单词。 3. `startsWith(prefix)`: 检查是否存在以给定前缀开头的单词。 Python中实现前缀树的一种常见方法是使用字典来表示节点,字典的键是字符,值是子节点。对于...

    leetcode常见的100热点算法题

    例如,"N-Queens"(八皇后问题)和"Word Search"(单词搜索)就是使用回溯法求解的例子。 4. **贪心算法**:贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的。如...

Global site tag (gtag.js) - Google Analytics