LeetCode 87,远看是字符串其实是搜索,你能做出来吗?

2024-03-21 14:18

本文主要是介绍LeetCode 87,远看是字符串其实是搜索,你能做出来吗?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文始发于个人公众号:TechFlow,原创不易,求个关注


今天是LeetCode专题第54篇文章,我们一起来看LeetCode 87题,Scramble String(爬行字符串)。

这题的官方难度是Hard,通过率33%,点赞506,反对702。看起来这题难度还可以,但是反对比点赞多,其实这题质量还不错,反对比较多我猜可能是因为题意稍稍有些复杂,理解起来不太容易,编码也偏难。但是这题如果是放在正式比赛中出现的话,都不叫事。

下面我们来看下题意。


题意


这题的题目叫做爬取字符串,看起来有些费解,其实这个爬取是题目中定义出来的一种操作,我们稍候结合样例来看很容易理解。首先,我们先把一个字符串拆分成二叉树的形式。

   great/    \gr    eat/ \    /  \
g   r  e   at/ \a   t

也就是我们随机的选择分段点,每次都将字符串分割成两个部分。有了这棵二叉树之后,我们就可以进行爬取操作了。所谓的爬取操作,也就是调换这棵二叉树当中某一个节点的左右孩子的顺序。比如假设我们选择了对gr这个节点进行爬取,那么得到的结果如下:

    rgeat/    \rg    eat/ \    /  \
r   g  e   at/ \a   t

我们还可以多次执行爬取,比如我们多次爬取操作之后可以得到一个全新的字符串rgtae.

    rgtae/    \rg    tae/ \    /  \
r   g  ta  e/ \t   a

rgeat和rgtae都是从原字符串great进行一系列爬取操作之后得到的,题目会给定两个字符串s1和s2,要求我们给出能否通过对s1爬取操作得到字符串s2?


题解


不知道大家看完题意是什么感觉,是否觉得有些棘手呢?

棘手归棘手,但题目的要求还是很明确的。还是老规矩,我们一点点来分析问题。首先,那个花里胡哨的爬取操作是一个可逆操作,也就是说如果字符串s1能够通过这些操作变成s2,那么同样s2也可以通过同样的操作变回s1。从更高的层面来说,它们其实是一样的,是同一个存在的两个状态。

进一步,如果大家学过图论相关的算法,对这块有所了解的话,那么这个问题还可以进一步变形。

假设我们最初的字符串是s,它通过一步爬取操作可以变成s1,s2和s3。那么我们可以把这些字符串都抽象成一张无向图当中的节点。可以看成是s和s1,s2和s3之间有一条边相连。所以字符串之间能否通过爬取转化的关系就变成了在图上是否联通的关系,这个问题也就变成了在一张无向图当中已知两点,请问这两点是否联通。这个问题就简单多了,我们遍历整张图就好了。

缩小到了图上遍历之后,整个问题其实已经出来了,遍历图无非两种方法,一种是深度优先搜索,一种是宽度优先搜索。这两种都是老掉牙的算法了,实在没什么稀奇的。在这题当中深搜宽搜都差不多,看你的喜好了。我个人是选择的深搜实现的。

对于字符串的爬取操作而言,一共有两种可能,一种是s1拆分之后的两个部分分别和s2同样位置的两个部分的字符串进行比较。还有一种可能是s1的前半部分和s2的后半部分,s1的后半部分和s2的前半部分判断。这两种情况其实是同一个节点在搜索树上的两个支路,相当于我们提前剪枝了,剪掉了不可能存在解的搜索子树,这个也是剪枝的常规做法。

大家可能感觉这个题意比较复杂,但是最后的代码也许要比大家想的要简单:

class Solution:def isScramble(self, s1: str, s2: str) -> bool:from collections import Counterdef determine(s1, s2):# 如果s1和s2构成的字符不同,那么直接排除c1 = Counter(list(s1))c2 = Counter(list(s2))return c1 == c2def dfs(s1, s2):# 如果要判断的s1和s2相等,返回Trueif s1 == s2:return Trueif not determine(s1, s2):return Falsen = len(s1)# 枚举拆分的位置将字符串拆分成两个部分for i in range(1, n):if dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:]) or dfs(s1[:i], s2[n-i:]) and dfs(s1[i:], s2[:n-i]):return Truereturn Falseif len(s1) != len(s2):return Falseif len(s1) == 0:return Truereturn dfs(s1, s2)

总结


今天的这道题就算是讲完了,虽然看起来涉及到各种字符串的操作,又是建树又是颠倒顺序什么的,但这题本质上其实是一道搜索题。只要对搜索问题稍微熟悉一点,做出这道题并不困难,这也是本题通过率其实不算低的原因。

在之前的文章当中也曾经提到过,不管是在LeetCode上也好,还是在acm赛场上也罢,一道看似是字符串的问题最后通过建模转化成其他的算法模型是家常便饭的事情。大家做题的时候一定要思维灵活,如果钻了牛角尖可能就解不出来了。

今天的文章到这里就结束了,如果喜欢本文的话,请来一波素质三连,给我一点支持吧(关注、转发、点赞)。

在这里插入图片描述

这篇关于LeetCode 87,远看是字符串其实是搜索,你能做出来吗?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/832866

相关文章

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满