leetcode87. Scramble String

BlackFlagBin 发布于2019-08-15 11:13 / 2443人阅读

摘要：允许对非叶结点的两个子节点进行旋转，且允许对多个非叶节点进行子节点的旋转操作。将该操作生成的新字符串成为。现在输入两个字符串，判断该两个字符串是否是。不仅要考虑数组的划分，还要考虑所有可能的旋转。

题目要求

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    
  gr    eat
 /     /  
g   r  e   at
           / 
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    
  rg    eat
 /     /  
r   g  e   at
           / 
          a   t
We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    
  rg    tae
 /     /  
r   g  ta  e
       / 
      t   a
We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

将一个字符串逐渐分解为一个叶节点为单个字母的树。允许对非叶结点的两个子节点进行旋转，且允许对多个非叶节点进行子节点的旋转操作。将该操作生成的新字符串成为scrambled string。现在输入两个字符串，判断该两个字符串是否是scrambled string。

思路和代码

在一开始，我的思路出现了局限性，我希望通过列出所有的s1可以生成的scrambled string来判断s2是否在该集合中。但是后序就会发现，如果要计算s1全部的scrambled string显然是非常不明智的。不仅要考虑数组的划分，还要考虑所有可能的旋转。
之后，我就想到了利用递归来判断二者究竟是不是互相旋转生成的。我们先从一次旋转来看，比如great和reatg，然后再进行一次旋转变成eratg。我们可以看到，reat和erat也是scrambled string。也就是说，我们只要找到合适的旋转点，并判断s1和s2在旋转点左右的子字符串是否互为scrambled string就行。

递归的代码非常简洁清晰。

    public boolean isScramble(String s1, String s2) {
        if(s1.equals(s2)) return true;
        int[] alpha = new int[26];
        for(int i = 0 ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 LeetCode_String Scramble Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67616.html

[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0
Leetcode PHP题解--D87 705. Design HashSet

摘要：题目链接题目分析设计一个哈希类。需要有添加元素函数，判断元素存在的函数，移除元素函数。思路这真的没什么好说的了我把要存的值作为数组的键存储。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D87 705. Design HashSet 题目链接 705. Design HashSet 题目分析设计一个哈希类。需要有add添加元素函数，contains判断元素存在的函数，remov...

why_rookie 2019-07-01 14:00 评论0 收藏0
[Leetcode] Divide Two Integers 整数整除

摘要：位操作法复杂度时间空间思路我们设想，本来应该的得到余，那么如果我们把忽略余数后分解一下，，也就是，也就是把商分解为，所以商的二进制是。我们可以不断的将乘的一次方，二次方，等等，直到找到最大那个次方，在这里是的四次方。 Divide Two Integers Divide two integers without using multiplication, division and m...

张春雷 2019-08-14 12:46 评论0 收藏0
2017-09-24 前端日报

摘要：前端日报精选未来布局之星更快地构建使用预解析以及深入的虚拟原理原来与是这样阻塞解析和渲染的怎样把网站升级到中文视频从谈函数式与响应式编程叶俊星系列三之烟花效果实现掘金的故事解剖表情动图的构成设计系列传统递归和尾调用的实现前端架构经 2017-09-24 前端日报精选未来布局之星Grid更快地构建DOM: 使用预解析, async, defer 以及 preload_JavaScri...

yuanzhanghu 2019-08-21 16:43 评论0 收藏0
别人家的面试题：统计“1”的个数

摘要：长话短说，让我们来看一道题统计的个数给定一个非负整数，对于任意，，计算的值对应的二进制数中的个数，将这些结果返回为一个数组。第二版本的时间复杂度是最后版本的时间复杂度是，是的二进制数中的的个数，介于之间。小胡子哥@Barret李靖给我推荐了一个写算法刷题的地方leetcode.com，没有ACM那么难，但题目很有趣。而且据说这些题目都来源于一些公司的面试题。好吧，解解别人公司的面试题...

SQC 2019-08-19 18:27 评论0 收藏0