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++实现词语搜索内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-17

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(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(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(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(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

photoshop的75个超级技巧[不可不看]

Photoshop之所以在拥有强大功能的同时依然保持了良好的使用性, 很大程度上应该归功于其整齐精练的界面和简单易用的可自定义性( 除了 它大量的工具和命令 ). 事实上,Photoshop中拥有大量令人惊异的"隐 藏"功能.无论你用过Photoshop多少年,都会不断发掘出越来越多的东 西.我怀疑会有谁宣称他知道关于Photoshop"所有"的东西( 可能ADOBE 的软件工程师要除外 ). 下面的75个技巧将会帮助你( 无论你是新手还是经验丰富的专家 )掌握Ph

Android Studio修改Log信息颜色的实现

在Android中支持六种Log类型,分别为Verbose,Info,Debug,Warn,Error和Assert. Verbose:英文含义是冗长的,啰嗦的.Verbose用来记录不重要的,一般的信息,通常不需要关注. Info:中通常记录一些需要用户关注的消息,重要程度比Verbose高. Warn:中则记录警告信息,这类信息通常表示应用执行过程中出现了一些问题,这些问题并不会导致整个应用崩溃,但可能会导致一些业务不能正常执行,因此需要用户重点关注,其重要程度比Info高. Error:则

JavaScript中使用sencha gridpanel 编辑单元格、改变单元格颜色

表格GridPanel概述 ExtJS中的表格功能非常强大,包括了排序.缓存.拖动.隐藏某一列.自动显示行号.列汇总.单元格编辑等实用功能. 表格由类Ext.grid.GridPanel定义,继承自Panel,其xtype为grid.ExtJS中,表格Grid必须包含列定义信息,并指定表格的数据存储器Store.表格的列信息由类Ext.grid.Column(以前是由Ext.grid.ColumnModel定义).而表格的数据存储器由Ext.data.Store定义,数据存储器根据解析的数据不同

jquery实现的鼠标拖动排序Li或Table

1.前端页面 复制代码 代码如下: <%@ Page Language="C#" AutoEventWireup="true" CodeFile="拖动排序Li或Table.aspx.cs" Inherits="拖动排序Li或Table" %> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http

JS及PHP代码编写八大排序算法

从学习数据结构开始就接触各种算法基础,但是自从应付完考试之后就再也没有练习过,当在开发的时候也是什么时候使用什么时候去查一下,现在在学习JavaScript,趁这个时间再把各种基础算法整理一遍,分别以JS和PHP语法的方式编写代码. 1.冒泡排序 原理:临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束 时间复杂度:平均情况:O(n2)  最好情况:O(n) 最坏情况:O(n2)

iOS中生成指定大小、指定颜色的二维码和条形码方法详解

iOS7.0之后可以利用系统原生 API 生成二维码, iOS8.0之后可以生成条形码, 系统默认生成的颜色是黑色. 在这里, 利用以下方法可以生成指定大小.指定颜色的二维码和条形码, 还可以添加背景颜色.阴影效果, 以下是具体方法. 一. 生成二维码 Avilable in iOS 7.0 and later 方法如下: #pragma mark - 生成二维码 //Avilable in iOS 7.0 and later + (UIImage *)qrCodeImageWithConten

对GridView的行加颜色并弹出Kindeditor的实现思路

前台代码: 复制代码 代码如下: <head runat="server"> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/> <title></title> <script type="text/javascript"> function tureDelete() { if (c

JS简单实现表格排序功能示例

本文实例讲述了JS简单实现表格排序功能的方法.分享给大家供大家参考,具体如下: 思路:遍历每个li,并把它们存放到数组中去,然后通过sort()方法进行排序,再插入 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="htt

微信小程序开发之视频播放器 Video 弹幕 弹幕颜色自定义实例

把录音的模块尝试过之后就想着微信小程序的视频播放会不会更有趣? 果然,微信小程序视频自带弹幕.是不是很爽,跟我一起来看看. 先上gif: 再上几张图: 1.视频播放器 2.选择弹幕颜色 3.弹幕来了... 1.视频播放器 微信已经封装的非常好.我这里只用了很简单的几个属性 由于以前没做过弹幕,看到danmu-list就激动了.而且只需要将弹幕内容加入集合即可. 弹幕列表的元素: { text: '第 1s 出现的红色弹幕',//文本 color: '#ff0000',//颜色 time: 1//

ASP.Net2.0 GridView 多列排序,显示排序图标,分页

最近在使用ASP.net 2.0的GridView 控件时,发现排序与分页功能Microsoft实现的都很简单,比如排序,在点击列名的时候来触发整页的PostBack,然后排序,但是在列头上没有一个显示升序降序的图标,这会让最终用户使用时很迷惑,因为不知道是升序了还是降序了,所以今天首先解决的第一问题就是升序降序在列上显示图标,第二要解决的问题是默认GridView按列排序只能排一列的,也就是不能进行多列排序,而在实际应用中仅仅按照一列来排序是不能满足业务需求的,第三是GridView 分页问题