2014
11-18

# LeetCode-Scramble String[动态规划]

### Scramble String

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.

\begin{Code}
f[n][i][j]} = (f[k][i][j] && f[n-k][i+k][j+k])
|| (f[k][i][j+n-k] && f[n-k][i+k][j])
\end{Code}

// LeetCode, Interleaving String
// 递归，会超时，仅用来帮助理解
// 时间复杂度O(n^6)，空间复杂度O(1)
class Solution {
public:
bool isScramble(string s1, string s2) {
return isScramble(s1.begin(), s1.end(), s2.begin());
}
private:
typedef string::iterator Iterator;
bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
auto length = distance(first1, last1);
auto last2 = next(first2, length);

if (length == 1) return *first1 == *first2;

for (int i = 1; i < length; ++i)
if ((isScramble(first1, first1 + i, first2)
&& isScramble(first1 + i, last1, first2 + i))
|| (isScramble(first1, first1 + i, last2 - i)
&& isScramble(first1 + i, last1, first2)))
return true;

return false;
}
};


// LeetCode, Interleaving String
// 动规，时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
bool isScramble(string s1, string s2) {
const int N = s1.size();
if (N != s2.size()) return false;

// f[n][i][j]，表示长度为n，起点为s1[i]和
// 起点为s2[j]两个字符串是否互为scramble
bool f[N + 1][N][N];
fill_n(&f[0][0][0], (N + 1) * N * N, false);

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[1][i][j] = s1[i] == s2[j];

for (int n = 1; n <= N; ++n) {
for (int i = 0; i + n <= N; ++i) {
for (int j = 0; j + n <= N; ++j) {
for (int k = 1; k < n; ++k) {
if ((f[k][i][j] && f[n - k][i + k][j + k]) ||
(f[k][i][j + n - k] && f[n - k][i + k][j])) {
f[n][i][j] = true;
break;
}
}
}
}
}
return f[N][0][0];
}
};


// LeetCode, Interleaving String
// 递归+剪枝
// 时间复杂度O(n^6)，空间复杂度O(1)
class Solution {
public:
bool isScramble(string s1, string s2) {
return isScramble(s1.begin(), s1.end(), s2.begin());
}
private:
typedef string::iterator Iterator;
bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
auto length = distance(first1, last1);
auto last2 = next(first2, length);
if (length == 1) return *first1 == *first2;

// 剪枝，提前返回
int A[26]; // 每个字符的计数器
fill(A, A + 26, 0);
for(int i = 0; i < length; i++) A[*(first1+i)-'a']++;
for(int i = 0; i < length; i++) A[*(first2+i)-'a']--;
for(int i = 0; i < 26; i++) if (A[i] != 0) return false;

for (int i = 1; i < length; ++i)
if ((isScramble(first1, first1 + i, first2)
&& isScramble(first1 + i, last1, first2 + i))
|| (isScramble(first1, first1 + i, last2 - i)
&& isScramble(first1 + i, last1, first2)))
return true;

return false;
}
};


// LeetCode, Interleaving String
// 递归+map做cache
// 时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
bool isScramble(string s1, string s2) {
cache.clear();
return isScramble(s1.begin(), s1.end(), s2.begin());
}
private:
typedef string::const_iterator Iterator;
map<tuple<Iterator, Iterator, Iterator>, bool> cache;

bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
auto length = distance(first1, last1);
auto last2 = next(first2, length);

if (length == 1) return *first1 == *first2;

for (int i = 1; i < length; ++i)
if ((getOrUpdate(first1, first1 + i, first2)
&& getOrUpdate(first1 + i, last1, first2 + i))
|| (getOrUpdate(first1, first1 + i, last2 - i)
&& getOrUpdate(first1 + i, last1, first2)))
return true;

return false;
}

bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
auto key = make_tuple(first1, last1, first2);
auto pos = cache.find(key);

return (pos != cache.end()) ?
pos->second : (cache[key] = isScramble(first1, last1, first2));
}
};


typedef string::const_iterator Iterator;
typedef tuple<Iterator, Iterator, Iterator> Key;
// 定制一个哈希函数
namespace std {
template<> struct hash<Key> {
size_t operator()(const Key & x) const {
Iterator first1, last1, first2;
tie(first1, last1, first2) = x;

int result = *first1;
result = result * 31 + *last1;
result = result * 31 + *first2;
result = result * 31 + *(next(first2, distance(first1, last1)-1));
return result;
}
};
}

// LeetCode, Interleaving String
// 递归+unordered_map做cache，比map快
// 时间复杂度O(n^3)，空间复杂度O(n^3)
class Solution {
public:
unordered_map<Key, bool> cache;

bool isScramble(string s1, string s2) {
cache.clear();
return isScramble(s1.begin(), s1.end(), s2.begin());
}

bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
auto length = distance(first1, last1);
auto last2 = next(first2, length);

if (length == 1)
return *first1 == *first2;

for (int i = 1; i < length; ++i)
if ((getOrUpdate(first1, first1 + i, first2)
&& getOrUpdate(first1 + i, last1, first2 + i))
|| (getOrUpdate(first1, first1 + i, last2 - i)
&& getOrUpdate(first1 + i, last1, first2)))
return true;

return false;
}

bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
auto key = make_tuple(first1, last1, first2);
auto pos = cache.find(key);

return (pos != cache.end()) ?
pos->second : (cache[key] = isScramble(first1, last1, first2));
}
};


1. 剪枝法数组应该是会越界的！为什么最后一种解法定制哈希最后要减1？求解，谢谢。

2. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。