# Any better solution?

• My AC code is as below. I think it's not very efficient. Is there any better solution?

``````class Solution {
private:
bool anagram(string &s1, string &s2){
if(s1.size() != s2.size()) return false;
unordered_map<char, int> m;
int n = s1.size();
for(int i = 0; i < n; ++i){
if(m.find(s1[i]) != m.end()){
++m[s1[i]];
}else{
m[s1[i]] = 1;
}
}
for(int i = 0; i < n; ++i){
if(m.find(s2[i]) != m.end()){
--m[s2[i]];
if(m[s2[i]] < 0){
return false;
}
}else{
return false;
}
}
return true;
}
public:
bool isScramble(string s1, string s2) {
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
int n = s1.size();
for(int i = 1; i < n; ++i){
string s11 = s1.substr(0, i);
string s12 = s1.substr(i, n - i);
string s21 = s2.substr(0, i);
string s22 = s2.substr(i, n - i);
string s23 = s2.substr(n - i, i);
string s24 = s2.substr(0, n - i);
if(anagram(s11, s21) && anagram(s12, s22) &&
isScramble(s11, s21) && isScramble(s12, s22)
||
anagram(s11, s23) && anagram(s12, s24) &&
isScramble(s11, s23) && isScramble(s12, s24)){
return true;
}
}
return false;
}
};
``````

The main idea is:

1. separate `s1` into two parts, namely `--s11--`, `--------s12--------`
2. separate `s2` into two parts, namely `--s21--`, `--------s22--------`, and test the corresponding part (`s11` and `s21` && `s12` and `s22`) with `isScramble`.
3. separate `s2` into two parts, namely `--------s23--------`, `--s24--`, and test the corresponding part (`s11` and `s24` && `s12` and `s23`) with `isScramble`.
4. Note that before testing each sub-part with `isScramble`, `anagram` is used first to test if the corresponding parts are anagrams. If not, skip directly.

• ``````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;
}
}
``````

This is my code which is more concise, while the idea is same.

• The idea is familiar. But my solution is dp algorithm. The time complexity is O(n^4).

``````class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if len(s1) != len(s2):
return False
elif len(s1) == 0:
return True
LEN = len(s1)
dp = [[[False] * LEN for start2 in xrange(0, LEN)] for start1 in xrange(0, LEN)]
for width in xrange(0, LEN):
for start1 in xrange(0, LEN-width):
for start2 in xrange(0, LEN-width):
if width == 0:
if s1[start1] == s2[start2]:
dp[start1][start2][width]=True
else:
for sep in xrange(0, width):
if dp[start1][start2][sep] and dp[start1+sep+1][start2+sep+1][width-sep-1]:
dp[start1][start2][width]=True
break
if dp[start1][start2+width-sep][sep] and dp[start1+sep+1][start2][width-sep-1]:
dp[start1][start2][width]=True
break
return dp[0][0][LEN-1]``````

• My solution is O(n^3)

It uses a O(n^3) extra space to save the results of every comparison.
The comparison here means that whether two strings are scramble to each other, if scramble, the comparison return true, vice versa.

Its time cost is Sum{k=0 ... n-1} (n-k)(n-k)(k+1) = O(n^3)

``````class Solution {
public:
typedef vector< vector<bool> > matrix;
vector<matrix> MAP;
string str1;
string str2;
bool isScramble(string s1, string s2) {
str1 = s1;
str2 = s2;
if(s1.size() != s2.size())
return false;
int size = s1.size();

matrix m;
vector<bool> v;
v.resize(size, false);
for(int i=0; i<size; i++)
m.push_back(v);

for(int i=0; i<size; i++)
MAP.push_back(m);

for(int i=1; i<=size; i++)
{
for(int x=0; x<=size-i; x++)
{
for(int y=0; y<=size-i; y++)
{
MAP[i-1][x][y] = compare(i, x, y);
}
}
}
return MAP[size-1][0][0];

}

bool compare(int substrLen, int s1Pos, int s2Pos)
{
int length = substrLen;
if(length == 1)
return str1[s1Pos] == str2[s2Pos];
if(length == 2)
{
return (str1[s1Pos]==str2[s2Pos]&&str1[s1Pos+1]==str2[s2Pos+1]) || (str1[s1Pos]==str2[s2Pos+1]&&str1[s1Pos+1]==str2[s2Pos]);
}

for(int i=1; i<length; i++)
{
bool test1 = MAP[i-1][s1Pos][s2Pos] && MAP[length-i-1][s1Pos+i][s2Pos+i];
if(test1)
return true;

bool test2 = MAP[i-1][s1Pos][s2Pos+length-i] && MAP[length-i-1][s1Pos+i][s2Pos];;
if(test2)
return true;
}
return false;
}

};``````

• According to my calculation, Sum{k=0 ... n-1} (n-k)(n-k)(k+1) = O(n^4)
The coefficient of n^4 is 1/12.

• Here is my solution, which has same idea but a little optimization, and takes nearly 20ms to pass all the tests.

``````class Solution {
private:
bool isDeformation(string &s1, string &s2)
{
if(s1.size() != s2.size())return false;
int albe[26] = {0};
for(int i = 0; i < s1.size(); i ++)
albe[s1[i] - 'a'] ++;
for(int i = 0; i < s2.size(); i ++)
{
albe[s2[i] - 'a'] --;
if(albe[s2[i] - 'a'] < 0)return false;
}
return true;
}
public:
bool isScramble(string s1, string s2) {
if(isDeformation(s1, s2))
{
int len = s1.size();
if(len <= 3) return true;
for(int i = 1; i < s1.size(); i ++)
{
string s11 = s1.substr(0, i);
string s12 = s1.substr(i, len-i);
if(isScramble(s11, s2.substr(0,i)) && isScramble(s12, s2.substr(i, len-i)))
return true;
if(isScramble(s11, s2.substr(len-i,i)) && isScramble(s12, s2.substr(0, len-i)))
return true;
}
}
return false;
}
};``````

• This is O(n^4)

• my solution is almost identical but cache isScramble result in a hash map, which improves performance as well.

• Your function isDeformation() is brilliant!!! I just check whether each character in s1 is in s2, if not, return false. Obviously your method could block out more false cases than mine!!
I copy and paste your method into mine, and I get optimisation from 80ms to 16ms.

• nice coding.

• C++ solution with bottom-up dynamic programming.

``````class Solution
{
public:

bool isScramble(string s1, string s2)
{
if (s1.length() != s2.length())
{
return false;
}

if (s1.empty())
{
return true;
}

size_t len = s1.length();
vector<vector<vector<bool>>> dp(len,
vector<vector<bool>>(len,
vector<bool>(len + 1,
false)));

for (size_t i = 0; i < len; ++i)
{
for (size_t j = 0; j < len; ++j)
{
dp[i][j][1] = (s1[i] == s2[j]);
}
}

for (size_t subLength = 2; subLength <= len; ++subLength)
{
for (size_t i = 0; i <= (len - subLength); ++i)
{
for (size_t j = 0; j <= (len - subLength); ++j)
{
for (size_t offset = 0;
(offset < (subLength - 1)) && !dp[i][j][subLength];
++offset)
{
size_t len1 = offset + 1;
size_t len2 = subLength - len1;

dp[i][j][subLength] =
(dp[i][j][len1] && dp[i + len1][j + len1][len2]) ||
(dp[i][j + len2][len1] && dp[i + len1][j][len2]);
}
}
}
}

return dp[0][0][len];
}
};
``````

• @ hongzhi, your code is great, and I got reminded of the second possiblity from your code. thank you.

• use two int with some bit manipulation can do the "isDeformation" work while save some memory.

• after some testing, bit manipulation takes too much time that it would TLE lol.

• Same recursion idea in Python:

``````class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if s1 == s2: return True
if sorted(s1) != sorted(s2): return False

for i in xrange(1, len(s1)):
ls1, rs1 = s1[:i], s1[i:]
ls2, rs2 = s2[:i], s2[i:]
rls2, rrs2 = s2[:-i], s2[-i:]

if (self.isScramble(ls1, ls2) and self.isScramble(rs1, rs2) or
self.isScramble(ls1, rrs2) and self.isScramble(rs1, rls2)):
return True

return False``````

• As far as I can tell, T(n) = O(nT(n-1)) = O(n!). Is this correct?

• Very elegant!!

• A more concise C++ DP version.
dp[i][j][l] means whether s2.substr(j,l) is a scrambled string of s1.substr(i,l) or not.

``````class Solution {
public:
bool isScramble(string s1, string s2) {
int len=s1.size();
bool dp[100][100][100]={false};
for (int i=len-1;i>=0;i--)
for (int j=len-1;j>=0;j--) {
dp[i][j][1]=(s1[i]==s2[j]);
for (int l=2;i+l<=len && j+l<=len;l++) {
for (int n=1;n<l;n++) {
dp[i][j][l]|=dp[i][j][n]&&dp[i+n][j+n][l-n];
dp[i][j][l]|=dp[i][j+l-n][n]&&dp[i+n][j][l-n];
}
}
}
return dp[0][0][len];
}
}; ``````

• My java solution is a bit longer. The basic idea is the same. But with some optimization. I used a single CharCountMap to determine if it's anagram instead of creating new map for every sub-string. also determine anagram in an incremental way
I also avoid creating many sub strings by using indexes.

``````public class Solution {
static class CharCountMap extends HashMap<Character, int[]> {
int[] i = get(c);
if(i == null) {
i = new int[1];
put(c, i);
}
i[0] += add ? +1 : -1;
if(i[0] == 0)
remove(c);
}
}

private static CharCountMap charCountMap;

public static boolean isScramble(String s1, String s2) {
charCountMap = new CharCountMap();
if(s1.length() != s2.length())
return false;

for(char c : s1.toCharArray())
for(char c : s2.toCharArray())
if(!charCountMap.isEmpty())
return false;

return isScramble(s1, 0, s2, 0, s2.length());
}

private static boolean isScramble(String s1, int p1, String s2, int p2, int length) {
if(s1.substring(p1, p1 + length).equals(s2.substring(p2, p2 + length)))
return true;

for(int i=1; i<length; i++){  //Partition
charCountMap.addChars(s1.charAt(p1 + i - 1), true);
charCountMap.addChars(s2.charAt(p2 + i - 1), false);
if(charCountMap.isEmpty())
if(isScramble(s1, p1, s2, p2, i) && isScramble(s1, p1 + i, s2, p2 + i, length - i))
return true;
}
charCountMap.clear();
for(int i=1; i<length; i++){  //Partition
charCountMap.addChars(s1.charAt(p1 + i - 1), true);
charCountMap.addChars(s2.charAt(p2 + length - i), false);
if(charCountMap.isEmpty())
if(isScramble(s1, p1, s2, p2 + length - i, i) && isScramble(s1, p1 + i, s2, p2, length - i))
return true;
}

return false;
}
}``````

• Well done sir

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.