1. 首页

LeetCode 087. 扰乱字符串

题目描述:

难度: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" 的一个扰乱字符串。

给出两个长度相等的字符串 s1s2 ,判断s2 是否是s1 的扰乱字符串。

示例1:

输入: s1 = "great", s2 = "rgeat"
输出: true

示例2:

输入: s1 = "abcde", s2 = "caebd"
输出: false

思路:

s1遍历,将s1s2分割为[0,i][i,length]

如果s1[0,i]s2[0,i]不是相同字母(相同字母指字母相同但顺序不一定相同),并且s1[0,i]s2[length-i,length]也不是相同字母,那么当前分割就是无效的。
继续遍历i,直到找出有效分割点。

注意,因此对于每一次分割点,只需要检查头和尾;

例如great

第一次分割有以下情况:

great,交换后,reatg

great,交换后,eatgr

great,交换后,atgre

great,交换后,tgrea

可以发现,交换前,左侧在左,右侧在右;交换后,左侧在右,右侧在左。

/**
 * @来源: 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, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 087. 扰乱字符串

链接:https://www.javascriptc.com/4447.html

« LeetCode 088. 合并两个有序数组
NODE.JS根据URL返回指定的图片»
Flutter 中文教程资源

相关推荐

QR code