问题描述:
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.
原问题链接:https://leetcode.com/problems/scramble-string/
问题分析
递归方法
从前面问题的定义里可以看到,如果一个字符串是另外一个字符串的变体的话,它里面的某些元素会在原来元素构成一个二叉树的样式的情况下做一些交换的变换。因为这个变换使得里面一部分元素的位置发生了变化。比如前面的"great",在转换成"rgtae"之后,实际上它是前面的两个元素换了个位置,而后面的元素的位置发生了两次转换一个是ea互换了位置,它们作为一个整体又和t换了位置。
光从上述的描述里来看不太好找问题的规律。我们这么来看,将原来的字符串拆成二叉树的表示,它其实是首先将字符拆成两部分,然后再对每一部分进一步细分的过程。比如对于字符串"great"来说,从第一级的划分情况来看,它可能有如下几种方式:
- 左子节点有0个元素
- 左节点有1个元素
- 左节点有2个元素
- 左节点有3个元素
- 左节点有4个元素
- 左节点有5个元素
在上述的各种划分情况中我们可以看到,它相当于在字符串里的任意一个位置对它进行了划分。而划分后的结果可能会进行进一步的划分和交换。 从上述最基本的情况来看,如果只是划分的话,修改后的字符串里的前面某一部分应该和之前同样索引范围内的字符串相同。而如果有交换的话呢,则可能是修改后的字符串里从后面往前的一部分串和前面串里从前往后的那部分串构成同样的关系。因为这里是划分和交换结合在一起的,所以它们构成一个如下的递归关系:
isScramble(s1, s2) => {
for(int i = 1; i < s1.length; i++) {
isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) return true;
if(isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) return true;
}
}
另外一方面,对于给定长度的两个串来说,它们是否为另外一个的变换,我们需要根据几个条件来判断,一个是它们的长度是否相等。另外一个它们最终的字符以及出现的次数是否一致。对于这个,需要将两个串排序并进行比较。
结合这两点,可以得到详细的代码实现如下:
public class Solution { public boolean isScramble(String s1, String s2) { if(s1 == null || s2 == null || s1.length() != s2.length()) return false; if(s1.equals(s2)) return true; char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); Arrays.sort(c1); Arrays.sort(c2); if(!Arrays.equals(c1, c2)) return false; for(int i = 1; i < s1.length(); i++) { if(isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) return true; if(isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) return true; } return false; } }
动态规划法
在上述讨论递归算法的问题时,我们会发现里面有若干个递归的子问题是有重叠的,它们被重复调用过若干次。那么,从动态规划的角度来说,可以对这些问题进行优化。于是我们就有一个如下的思路:
假设F(i, j, k)表示s1的子串s1[i..i + k - 1]是否为s2的子串s2[j..j + k - 1]的变体。既然在前面的二叉树表示中,字符串中每个节点都有可能成为潜在的划分点,我们需要检查所有可能的划分点情况。也就是前面问题中描述的那几种示例情况。
假设q是某一段划分的长度(q < k),那么这个划分将有这么几种情况:
对于s2来说,它对应有两种情况:
或者
根据上述的讨论,我们发现它们满足一个如下的关系:
对于某个长度q来说(1 <= q < k),F(i, j, k) = (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
这个问题的推导其实和前面递归的过程类似,我们需要针对所有的情况进行遍历。详细的代码实现如下:
public class Solution { public boolean isScramble(String s1, String s2) { if (s1.length() != s2.length()) return false; int len = s1.length(); boolean [][][] F = new boolean[len][len][len + 1]; for (int k = 1; k <= len; ++k) for (int i = 0; i + k <= len; ++i) for (int j = 0; j + k <= len; ++j) if (k == 1) F[i][j][k] = s1.charAt(i) == s2.charAt(j); else for (int q = 1; q < k && !F[i][j][k]; ++q) { F[i][j][k] = (F[i][j][q] && F[i + q][j + q][k - q]) || (F[i][j + k - q][q] && F[i + q][j][k - q]); } return F[0][0][len]; } }
参考材料
https://leetcode.com/discuss/85424/simple-iterative-dp-java-solution-with-explanation
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum ...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
leetcode 1004 力码 去做 : array , dynamic-programming : link , math : string , sliding-window : array , median : string : string : number , reverse , bit : string : math , bit : string , ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
leetcode 持续刷leetcode中... 欢迎大家交流,也欢迎star. ...Leetcode 767: Reorganize String Leetcode 769: Max Chunks To Make Sorted Leetcode 792: Number of Matching Subsequences Leetcode 794: Valid
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题