`
cozilla
  • 浏览: 92075 次
  • 性别: 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

    c c语言_leetcode题解之0079_word_search.zip

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

    javascript js_leetcode题解之79-word-search.js

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

    c语言入门 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-...

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

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

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

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

    _leetcode-python.pdf

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

    LeetCode各公司题目合集

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

    算法刷题笔记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. **贪心算法**:贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的。如...

    c++-c++编程基础之leetcode题解第79题单词搜索.zip

    在本压缩包中,主题聚焦于C++编程基础与LeetCode题解,特别是关于第79题“单词搜索”(Word Search)。LeetCode是一个在线平台,它提供了许多编程题目,帮助开发者提升算法技能和问题解决能力。让我们深入探讨C++...

    leetcode耗时-word-search-ii:查词二

    leetcode 耗时查词二 给定一个 2D 板和字典中的单词列表,找到板中的所有单词。 每个单词必须由顺序相邻单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能在一个单词中多次使用...

Global site tag (gtag.js) - Google Analytics