https://leetcode.com/problems/scramble-string
Given a strings1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1=
"great":great / \ gr eat / \ / \ g r e at / \ a tTo 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 tWe 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 aWe 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.
To scramble the string, we may choose any non-leaf node and swap its two children.
题眼：也就是假如 str1 和 str2 是scramble 得到的， 那么 就相当于 把str1 分成 str1_L 和 str1_R, 把str2 分成 str2_L 和 str2_R.
那么
1 要么 str1_L is a scrambled string of str2_L && str1_R is a scrambled string of str2_R
2 要么 str1_L is a scrambled string of str2_R && str1_R is a scrambled string of str2_L (经过了一次swap children)
method1: 自然可以得到递归 dfs 暴力解法 （但是有助于思路）： ==> 192 / 282 test cases passed.
public boolean isScramble(String s1, String s2) {
// corner case
if (s1 == null || s2 == null) {
return s1 == s2;
}
if (s1.length() == 0 || s2.length() == 0) {
return s1.length() == s2.length();
}
// quick fail
if (s1.length() != s2.length()) {
return false;
}
int n = s1.length();
if (n == 1) {
return s1.equals(s2);
}
for (int l = 1; l < n; ++l) {
// case 1
if (isScramble(s1.substring(0, l), s2.substring(0, l)) && isScramble(s1.substring(l), s2.substring(l))) {
return true;
}
// case 2
if (isScramble(s1.substring(0, l), s2.substring(n - l)) && isScramble(s1.substring(l), s2.substring(0, n - l))) {
return true;
}
}
return false;
}
method2: 不用substring， 利用two pointers 表示substring : ==> 208 / 282 test cases passed.
public boolean isScramble(String s1, String s2) {
// corner case handle
if (s1 == null || s2 == null) {
return s1 == s2;
}
if (s1.length() == 0 || s2.length() == 0) {
return s1.length() == s2.length();
}
if (s1.length() != s2.length()) {
return false;
}
int n = s1.length();
return dfs(s1.toCharArray(), 0, n - 1, s2.toCharArray(), 0, n - 1);
}
private boolean dfs(char[] str1, int s1, int e1, char[] str2, int s2, int e2) {
// try every possible cases
if (s1 == e1) {
return str1[s1] == str2[s2];
}
int n = e1 - s1 + 1;
for (int l = 1; l < n; ++l) {
if (dfs(str1, s1, s1 + l - 1, str2, s2, s2 + l - 1) && dfs(str1, s1 + l, e1, str2, s2 + l, e2)) {
return true;
}
if (dfs(str1, s1, s1 + l - 1, str2, e2 - l + 1, e2) && dfs(str1, s1 + l, e1, str2, s2, e2 - l)) {
return true;
}
}
return false;
}
method3: 超时是因为重复计算子结构 -> memoization （记忆化搜索） ==》 Accepted
仅仅就是多了一个 Boolean[][][] mem;
public class Solution {
Boolean[][][] mem;
public boolean isScramble(String s1, String s2) {
// corner case handle
if (s1 == null || s2 == null) {
return s1 == s2;
}
if (s1.length() == 0 || s2.length() == 0) {
return s1.length() == s2.length();
}
if (s1.length() != s2.length()) {
return false;
}
int n = s1.length();
mem = new Boolean[n + 1][n][n];
return dfs(s1.toCharArray(), 0, n - 1, s2.toCharArray(), 0, n - 1);
}
private boolean dfs(char[] str1, int s1, int e1, char[] str2, int s2, int e2) {
// try every possible cases
if (s1 == e1) {
mem[1][s1][s2] = (str1[s1] == str2[s2]);
return mem[1][s1][s2];
}
int n = e1 - s1 + 1;
if (mem[n][s1][s2] != null) {
return mem[n][s1][s2];
}
for (int l = 1; l < n; ++l) {
if (dfs(str1, s1, s1 + l - 1, str2, s2, s2 + l - 1) && dfs(str1, s1 + l, e1, str2, s2 + l, e2)) {
mem[n][s1][s2] = true;
return true;
}
if (dfs(str1, s1, s1 + l - 1, str2, e2 - l + 1, e2) && dfs(str1, s1 + l, e1, str2, s2, e2 - l)) {
mem[n][s1][s2] = true;
return true;
}
}
mem[n][s1][s2] = false;
return false;
}
}
method4: 既然可以用memoization (top down)那么也肯定可以用DP (bottom up)
完全可以对照着上面快速写出来
public class Solution {
public boolean isScramble(String s1, String s2) {
// corner case handle
if (s1 == null || s2 == null) {
return s1 == s2;
}
if (s1.length() == 0 || s2.length() == 0) {
return s1.length() == s2.length();
}
if (s1.length() != s2.length()) {
return false;
}
int n = s1.length();
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
boolean[][][] mem = new boolean[n + 1][n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
mem[1][i][j] = str1[i] == str2[j];
}
}
for (int ln = 2; ln <= n; ++ln) {
for(int i = 0; i <= n - ln; ++i) {
for (int j = 0; j <= n - ln; ++j) {
for (int l = 1; l < ln; ++l) {
if (mem[l][i][j] && mem[ln-l][i+l][j+l]) {
mem[ln][i][j] = true;
}
if (mem[l][i][j+ln-l] && mem[ln-l][i+l][j]) {
mem[ln][i][j] = true;
}
}
}
}
}
return mem[n][0][0];
}
}