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.
Solution 1: Use DP, dp[i][j][k] means s1[i...i+k] & s2[j...j+k] is scramble string or not. It need 3 loop to iterate the dp array and another loop to calculate the dp[i][j][k], so complexity is O(n^4).
public class Solution {
public boolean isScramble(String s1, String s2) {
int n=s1.length();
if (n!=s2.length()) return false;
boolean[][][] dp=new boolean[n][n][n];
for (int i=n-1; i>=0; i--) {
for (int j=n-1; j>=0; j--) {
for (int k=0; i+k<n && j+k<n; k++) {
if (k==0) dp[i][j][k]=s1.charAt(i)==s2.charAt(j);
else {
dp[i][j][k]=false;
for (int t=0; t<k; t++) {
if ((dp[i][j][t] && dp[i+t+1][j+t+1][k-t-1]) || (dp[i][j+k-t][t] && dp[i+t+1][j][k-t-1])) {
dp[i][j][k]=true;
break;
}
}
}
}
}
}
return dp[0][0][n-1];
}
}
没有评论:
发表评论