C++实现LeetCode(79.词语搜索)

[LeetCode] 79. 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.

这道题是典型的深度优先遍历 DFS 的应用,原二维数组就像是一个迷宫,可以上下左右四个方向行走,我们以二维数组中每一个数都作为起点和给定字符串做匹配,我们还需要一个和原数组等大小的 visited 数组,是 bool 型的,用来记录当前位置是否已经被访问过,因为题目要求一个 cell 只能被访问一次。如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等,则对其上下左右四个邻字符分别调用 DFS 的递归函数,只要有一个返回 true,那么就表示可以找到对应的字符串,否则就不能找到,具体看代码实现如下:

解法一:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = search(board, word, idx + 1, i - 1, j, visited)
                 || search(board, word, idx + 1, i + 1, j, visited)
                 || search(board, word, idx + 1, i, j - 1, visited)
                 || search(board, word, idx + 1, i, j + 1, visited);
        visited[i][j] = false;
        return res;
    }
};

我们还可以不用 visited 数组,直接对 board 数组进行修改,将其遍历过的位置改为井号,记得递归调用完后需要恢复之前的状态,参见代码如下:

解法二:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[idx]) return false;
        char c = board[i][j];
        board[i][j] = '#';
        bool res = search(board, word, idx + 1, i - 1, j)
                 || search(board, word, idx + 1, i + 1, j)
                 || search(board, word, idx + 1, i, j - 1)
                 || search(board, word, idx + 1, i, j + 1);
        board[i][j] = c;
        return res;
    }
};

到此这篇关于C++实现LeetCode(79.词语搜索)的文章就介绍到这了,更多相关C++实现词语搜索内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • C++实现LeetCode(85.最大矩形)

    [LeetCode] 85. Maximal Rectangle 最大矩形 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Example: Input: [ ["1","0","1","0","0"], ["1

  • C++实现LeetCode(71.简化路径)

    [LeetCode] 71.Simplify Path 简化路径 Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases

  • C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • C++实现LeetCode(75.颜色排序)

    [LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

  • C++实现LeetCode(72.编辑距离)

    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

  • C++实现LeetCode(76.最小窗口子串)

    [LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

  • C++实现LeetCode(79.词语搜索)

    [LeetCode] 79. 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. Th

  • C++实现LeetCode(127.词语阶梯)

    [LeetCode] 127.Word Ladder 词语阶梯 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transforme

  • C++实现LeetCode(126.词语阶梯之二)

    [LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed

  • C++实现LeetCode(642.设计搜索自动补全系统)

    [LeetCode] 642. Design Search Autocomplete System 设计搜索自动补全系统 Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you ne

  • 实现支持逻辑搜索/单词搜索/词组搜索+支持OR/AND关键字的VBS CLASS!

    CLASS功能.替换传入的字符串成为SQL语句Where关键字后面的表达式: 词语搜索 [例如: 小明] 词组搜索  词组里面每一个词都将被检索  例如: 小强1 小名1 小强强 小小强 逻辑搜索  支持 And 和 Or 运算符.  例如: 小明 And 小强 And 小小强 复合条件: 例如:(小小明 Or 小明) And (小强 Or 小小强)  例如:(小小明 Or 小名) And 小小强 例如: ROOT1 And (广东人 Or 北京人)  ---------------------

  • 使用Clion刷LeetCode的方法

    首先创建一个project,我这里取名为LeetCode. 安装leetcode editor插件,File–>Settings–>Plugins,直接搜索leetcode就出来了,安装完了记得重启一下IDE. 设置LeetCode用户名和密码 CodeFileName: $!{question.frontendQuestionId}-${question.titleSlug} CodeTemplate: ${question.content} \#include<bits/stdc++

  • C++ leetcode之删除并获得点数的示例代码

    参考链接 https://leetcode-cn.com/problems/delete-and-earn/ https://leetcode-cn.com/problems/delete-and-earn/solution/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/ 题目描述 给你一个整数数组 nums ,你可以对它进行一些操作. 每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数.之后,你必须删除每个等于 num

  • vscode刷acm、leetcode的题目

    目录 简介 编译器 Windows 使用 Code Runner 插件运行代码 使用 C/C++ 插件编译并调试 安装插件 配置编译 配置 GDB/LLDB 调试器 开始调试代码 简介 Visual Studio Code(以下简称 VS Code) 是一个由微软开发,同时支持 Windows.Linux 和 macOS 等操作系统且开放源代码的代码编辑器.它是用 TypeScript 编写的,并且采用 Electron 架构.它带有对 JavaScript.TypeScript 和 Node.

  • 详解Spring Boot 中使用 Java API 调用 lucene

    Lucene是apache软件基金会4 jakarta项目组的一个子项目,是一个开放源代码的全文检索引擎工具包,但它不是一个完整的全文检索引擎,而是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎(英文与德文两种西方语言).Lucene的目的是为软件开发人员提供一个简单易用的工具包,以方便的在目标系统中实现全文检索的功能,或者是以此为基础建立起完整的全文检索引擎 全文检索概述 比如,我们一个文件夹中,或者一个磁盘中有很多的文件,记事本.world.Excel.pdf,我们

  • C++实现LeetCode(35.搜索插入位置)

    [LeetCode] 35. Search Insert Position 搜索插入位置 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example

随机推荐