Problem: We can scramble a string s to get a string t using the following algorithm:
- If the length of the string is 1, stop.
- If the length of the string is > 1, do the following:
- Split the string into 2 non-empty substrings at a random index, i.e. if the string is s, divide it to x and y where s = x + y.
- Randomly, decide to swap the two substrings or to keep them in the same order. i.e. after this step, s may become s = x + y or s = y + x.
- Apply step 1 recursively on each of the two substrings x and y.
Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
Approach: Divide and Conquer. If S2 is a scrambled form of S1, then there must exist an index i such that at least one of the following conditions is true:
- S2[0…i] is a scrambled string of S1[0…i] and S2[i+1…n] is a scrambled string of S1[i+1…n].
- S2[0…i] is a scrambled string of S1[n-i…n] and S2[i+1…n] is a scrambled string of S1[0…n-i-1].
public bool IsScramble(string s1, string s2)
{
if (s1.Length != s2.Length)
{
return false;
}
if (s1.Length == 0)
{
return true;
}
if (s1 == s2)
{
return true;
}
// Just an optimization
if (!this.AreAnangrams(s1, s2))
{
return false;
}
for (int i = 1; i < s1.Length; ++i)
{
if (this.IsScramble(s1.Substring(0, i), s2.Substring(0, i))
&& this.IsScramble(s1.Substring(i, s1.Length - i), s2.Substring(i, s2.Length - i)))
{
return true;
}
if (this.IsScramble(s1.Substring(0, i), s2.Substring(s2.Length - i, i))
&& this.IsScramble(s1.Substring(i, s1.Length - i), s2.Substring(0, s2.Length - i)))
{
return true;
}
}
return false;
}
public bool AreAnangrams(string s1, string s2)
{
if (s1.Length != s2.Length)
{
return false;
}
char[] s1Arr = s1.ToCharArray();
char[] s2Arr = s2.ToCharArray();
Array.Sort(s1Arr);
Array.Sort(s2Arr);
for (int i = 0; i < s1Arr.Length; ++i)
{
if (s1Arr[i] != s2Arr[i])
{
return false;
}
}
return true;
}
Complexity - 2^n. (exponential)
Approach 2: Use DP.
public bool IsScrambleDynamic(string s1, string s2)
{
if (s1.Length != s2.Length)
{
return false;
}
if (s1.Length == 0)
{
return true;
}
if (s1 == s2)
{
return true;
}
if (!this.AreAnangrams(s1, s2))
{
return false;
}
int totalLength = s1.Length;
bool[,,] table = new bool[totalLength + 1, totalLength, totalLength];
// len = 0 so true
table[0, 0, 0] = true;
// for len = 1
for (int s1Index = 0; s1Index < totalLength; ++s1Index)
{
for (int s2Index = 0; s2Index < totalLength; ++s2Index)
{
table[1, s1Index, s2Index] = s1[s1Index] == s2[s2Index];
}
}
// for len = 2...totalLength
bool scrambled = false;
for (int len = 2; len <= totalLength; ++len)
{
for (int s1Index = totalLength - len; s1Index >= 0; --s1Index)
{
for (int s2Index = totalLength - len; s2Index >= 0; --s2Index)
{
for (int leftLen = 1; leftLen < len; ++leftLen)
{
int rightLen = len - leftLen;
scrambled = (table[leftLen, s1Index, s2Index] && table[rightLen, s1Index + leftLen, s2Index + leftLen]) ||
(table[leftLen, s1Index, s2Index + rightLen] && table[rightLen, s1Index + leftLen, s2Index]);
if (scrambled)
break;
}
table[len, s1Index, s2Index] = scrambled;
}
}
}
return table[totalLength, 0, 0];
}
Complexity: n^4
No comments:
Post a Comment