LeetCode 87，远看是字符串其实是搜索，你能做出来吗？
365bet体育在线始发于个人公众号：TechFlow，原创不易，求个关注
今天是LeetCode专题第54篇文章，365bet体育在线们一起来看LeetCode 87题，Scramble String（爬行字符串）。
这题的官方难度是Hard，通过率33%，点赞506，反对702。看起来这题难度还可以，但是反对比点赞多，其实这题质量还不错，反对比较多365bet体育在线猜可能是因为题意稍稍有些复杂，理解起来不太容易，编码也偏难。但是这题如果是放在正式比赛中出现的话，都不叫事。
下面365bet体育在线们来看下题意。
题意
这题的题目叫做爬取字符串，看起来有些费解，其实这个爬取是题目中定义出来的365体育投注操作，365bet体育在线们稍候结合样例来看很容易理解。首先，365bet体育在线们先把一个字符串拆分成二叉树的形式。
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
也就是365bet体育在线们随机的选择分段点，每次都将字符串分割成两个部分。有了这棵二叉树之后，365bet体育在线们就可以进行爬取操作了。所谓的爬取操作，也就是调换这棵二叉树当中某一个节点的左右孩子的顺序。比如假设365bet体育在线们选择了对gr这个节点进行爬取，那么得到的结果如下：
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
365bet体育在线们还可以多次执行爬取，比如365bet体育在线们多次爬取操作之后可以得到一个全新的字符串rgtae.
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
rgeat和rgtae都是从原字符串great进行一系列爬取操作之后得到的，题目会给定两个字符串s1和s2，要求365bet体育在线们给出能否通过对s1爬取操作得到字符串s2？
题解
不知道大家看完题意是什么感觉，是否觉得有些棘手呢？
棘手归棘手，但题目的要求还是很明确的。还是老规矩，365bet体育在线们一点点来分析问题。首先，那个花里胡哨的爬取操作是一个可逆操作，也就是说如果字符串s1能够通过这些操作变成s2，那么同样s2也可以通过同样的操作变回s1。从更高的层面来说，它们其实是一样的，是同一个存在的两个状态。
进一步，如果大家学过图论相关的算法，对这块有所了解的话，那么这个问题还可以进一步变形。
假设365bet体育在线们最初的字符串是s，它通过一步爬取操作可以变成s1，s2和s3。那么365bet体育在线们可以把这些字符串都抽象成一张无向图当中的节点。可以看成是s和s1，s2和s3之间有一条边相连。365bet体育在线字符串之间能否通过爬取转化的关系就变成了在图上是否联通的关系，这个问题也就变成了在一张无向图当中已知两点，请问这两点是否联通。这个问题就简单多了，365bet体育在线们遍历整张图就好了。
缩小到了图上遍历之后，整个问题其实已经出来了，遍历图无非两种方法，365体育投注是深度优先搜索，365体育投注是宽度优先搜索。这两种都是老掉牙的算法了，实在没什么稀奇的。在这题当中深搜宽搜都差不多，看你的喜好了。365bet体育在线个人是选择的深搜实现的。
对于字符串的爬取操作而言，一共有两种可能，365体育投注是s1拆分之后的两个部分分别和s2同样位置的两个部分的字符串进行比较。还有365体育投注可能是s1的前半部分和s2的后半部分，s1的后半部分和s2的前半部分判断。这两种情况其实是同一个节点在搜索树上的两个支路，相当于365bet体育在线们提前剪枝了，剪掉了不可能存在解的搜索子树，这个也是剪枝的常规做法。
大家可能感觉这个题意比较复杂，但是最后的代码也许要比大家想的要简单：
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
from collections import Counter
def determine(s1, s2):
# 如果s1和s2构成的字符不同，那么直接排除
c1 = Counter(list(s1))
c2 = Counter(list(s2))
return c1 == c2
def dfs(s1, s2):
# 如果要判断的s1和s2相等，返回True
if s1 == s2:
return True
if not determine(s1, s2):
return False
n = 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 True
return False
if len(s1) != len(s2):
return False
if len(s1) == 0:
return True
return dfs(s1, s2)
总结
今天的这道题就算是讲完了，虽然看起来涉及到各种字符串的操作，又是建树又是颠倒顺序什么的，但这题本质上其实是一道搜索题。只要对搜索问题稍微熟悉一点，做出这道题并不困难，这也是本题通过率其实不算低的原因。
在之前的文章当中也曾经提到过，不管是在LeetCode上也好，还是在acm赛场上也罢，一道看似是字符串的问题最后通过建模转化成其他的算法模型是家常便饭的事情。大家做题的时候一定要思维灵活，如果钻了牛角尖可能就解不出来了。
今天的文章到这里就结束了，如果喜欢365bet体育在线的话，请来一波素质三连，给365bet体育在线一点支持吧（关注、转发、点赞）。
365bet体育在线使用 mdnice 排版