给定一个字符串 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
思路
- 两个字符串，全局搜索
- 单元子问题：两个字符是否相等
- 递归算法
- 递归结束判断
- 字符串是否为空
- 字符串长度是否相等
- 字符串直接相等
- 字符串包含字符数量和种类是否一致
- 字符串遍历，从1开始
- 递归匹配字串
- 递归1 0～i 和 0～i匹配 && i
len 和 ilen匹配 - 递归2 0
i 和 len-ilen匹配 && ilen 和 0len-i匹配
- 递归1 0～i 和 0～i匹配 && i
- 递归匹配字串
- 递归结束判断
代码
- 全局递归
class Solution {
public boolean isScramble(String s1, String s2) {
// 在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
// 全局递归匹配、问题细化、递归完成
if (s1 == null || s2 == null) return false;
if (s1.length() != s2.length()) return false;
if (s1.equals(s2)) return true;
int[] chs = new int[26];
int len = s1.length();
for (int i = 0;i < len;i++) {
chs[s1.charAt(i) - 'a']++;
chs[s2.charAt(i) - 'a']--;
}
for (int i = 0;i < 26;i++) {
if (chs[i] != 0) {
return false;
}
}
// 从1可开始，要不然会死循环
for (int i = 1;i < len;i++) {
// 正常情况 0~i 0~i && i~len i~len
if (isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i))) {
return true;
}
// 发生了交换 0~i len-i~len && i~len 0~len-i
if (isScramble(s1.substring(0,i),s2.substring(len-i)) && isScramble(s1.substring(i),s2.substring(0,len-i))) {
return true;
}
}
return false;
}
}
//
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1 == null || s2 == null) return false;
if (s1.length() != s2.length()) return false;
if (s1.equals(s2)) return true;
int[] letters = new int[26];
for (int i = 0; i < s1.length(); i++) {
letters[s1.charAt(i) - 'a']++;
letters[s2.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (letters[i] != 0) 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;
}
}
// 作者：powcai
// 链接：https://leetcode-cn.com/problems/scramble-string/solution/di-gui-by-powcai/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 动态规划
- dp[len][i][j]代表s1与s2的两个长度为len的片段是否是为扰乱字符串对
其中，s1以i起始，s2以j起始，也就是
s1[i:(i + len - 1)],s2[j:(j + len - 1)]这两段。 - 状态转移方程为：
dp[len][j][j] ||= (dp[k][i][j] && dp[len - k][i + k][j + k]) || (dp[k][i][j + len - k] && dp[len - k][i + k][j])其中
k>=1且k < len
空间复杂度O(N^3)，时间复杂度O(N^4) - 算法
- 状态初始化
- N+1 层状态
- 第一层 逐个位置匹配
- 枚举状态更新
- 层循环 len
- s1 循环 i
- s2循环 j
- 遍历已经确定状态的层 k
- 正常匹配状态更新
- 扰乱匹配状态更新
- 遍历已经确定状态的层 k
- s2循环 j
- s1 循环 i
- 层循环 len
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
if (s1.empty()) return true;
int N = s1.size();
// 三维动态数组，存储状态
vector<vector<vector<bool> > > dp(N + 1, vector<vector<bool> >(N, vector<bool>(N, false)));
// 初始化
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dp[1][i][j] = s1[i] == s2[j];
}
}
for (int len = 2; len <= N; ++len) { // len 2～N
for (int i = 0; i < N && i + len - 1 < N; ++i) { // i 0~N-1
for (int j = 0; j < N && j + len - 1 < N; ++j) {// j 0~N-1
for (int k = 1; k < len; ++k) { // k 1~len-1
if (dp[k][i][j] && dp[len - k][i + k][j + k]) {
dp[len][i][j] = true;
break;
}
if (dp[k][i][j + len - k] && dp[len - k][i + k][j]) {
dp[len][i][j] = true;
break;
}
}
}
}
}
return dp[N][0][0];
}
};
// 作者：da-li-wang
// 链接：https://leetcode-cn.com/problems/scramble-string/solution/c-dong-tai-gui-hua-by-da-li-wang-36/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
// java 版
class Solution {
public boolean isScramble(String s1, String s2) {
// 在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
// 全局递归匹配、问题细化、递归完成
if (s1 == null || s2 == null) return false;
if (s1.length() != s2.length()) return false;
if (s1.equals(s2)) return true;
int N = s1.length();
boolean[][][] dp = new boolean[N+1][N][N];
// 初始化状态
for (int i = 0;i < N;i++) {
for(int j = 0;j < N;j++) {
// dp[1][i][j] 第一层 记录 s[i] 与 s[j] 是否相等
dp[1][i][j] = s1.charAt(i) == s2.charAt(j);
}
}
// 枚举 字符片段是否 全局匹配
for (int len = 2; len <= N;len++) {
for (int i = 0;i < N && i + len - 1 < N;i++) {
for (int j = 0;j < N && j + len - 1 < N;j++) {
for (int k = 1; k < len;k++) {
if (dp[k][i][j] && dp[len - k][i + k][j + k]) {
dp[len][i][j] = true;
break;
}
if (dp[k][i][j + len - k] && dp[len - k][i + k][j]) {
dp[len][i][j] = true;
break;
}
}
}
}
}
return dp[N][0][0];
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
