题目描述:
难度:Hard
相关话题:字符串
、动态规划
给定一个字符串s1 ,我们可以把它递归地分割成两个非空子字符串,从而将其表示为二叉树。
下图是字符串s1 = "great"
的一种可能的表示形式。
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
在扰乱这个字符串的过程中,我们可以挑选任何一个非叶节点,然后交换它的两个子节点。
例如,如果我们挑选非叶节点 "gr"
,交换它的两个子节点,将会产生扰乱字符串 "rgeat"
。
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
我们将 "rgeat”
称作 "great"
的一个扰乱字符串。
同样地,如果我们继续将其节点 "eat"
和 "at"
进行交换,将会产生另一个新的扰乱字符串 "rgtae"
。
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
我们将 "rgtae”
称作 "great"
的一个扰乱字符串。
给出两个长度相等的字符串 s1 和s2 ,判断s2 是否是s1 的扰乱字符串。
示例1:
输入: s1 = "great", s2 = "rgeat"
输出: true
示例2:
输入: s1 = "abcde", s2 = "caebd"
输出: false
思路:
对s1
遍历,将s1
和s2
分割为[0,i]
,[i,length]
;
如果s1[0,i]
与s2[0,i]
不是相同字母(相同字母指字母相同但顺序不一定相同),并且s1[0,i]
与s2[length-i,length]
也不是相同字母,那么当前分割就是无效的。
继续遍历i
,直到找出有效分割点。
注意,因此对于每一次分割点,只需要检查头和尾;
例如great
,
第一次分割有以下情况:
g
,reat
,交换后,reat
,g
gr
,eat
,交换后,eat
,gr
gre
,at
,交换后,at
,gre
grea
,t
,交换后,t
,grea
可以发现,交换前,左侧在左,右侧在右;交换后,左侧在右,右侧在左。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var isScramble = function(s1, s2) {
if(s1===s2)return true
let hashCheck=check(s1,s2)
if(!hashCheck)return false
let len=s1.length
for(let i=1;i<len;i++){
let result=false
let left1=s1.substring(0,i),right1=s1.substring(i),
left2=s2.substring(0,i),right2=s2.substring(i)
result=isScramble(left1,left2) && isScramble(right1,right2) ||
isScramble(left1,s2.substring(len-i)) && isScramble(right1,s2.substring(0,len-i))
if(result)return true
}
return false
function check(s1,s2){
let hash={}
for(let n of s1){
if(hash[n]==null)hash[n]=1
else hash[n]++
}
for(let n of s2){
if(!hash[n])return false
else hash[n]--
}
return true
}
};
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com