博文中会简要介绍Leetcode P0087题目分析及解题思路。
“Scramble String”是一道比较难的动态规划题目，这道题的难点在于寻找最优子结构。这道题最终是一个高维动态规划，寻找最优子结构相对而言比较难，反而是最终的递推式逻辑简单，并不复杂。
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.
这道题的核心思路和递推式写法均以在Java和C++代码中详细注释，这里不再赘述。
以下是Java的题解代码实现。
class Solution {
public boolean isScramble(String s1, String s2) {
int n = s1.length();
if (n == 0)
return true;
if (n == 1)
return s1.equals(s2);
boolean[][][] dp = new boolean[n+1][n][n];
for (int i1=0; i1<n; ++i1) {
for (int j2=0; j2<n; ++j2)
dp[1][i1][j2] = (s1.charAt(i1) == s2.charAt(j2));
}
// dp[len][i][j]来表示s1[i, i+len)和s2[j, j+len)两个字符串是否满足条件.
// 换句话说，就是S1从i开始的len个字符是否能转换为S2从j开始的len个字符
for (int len=2; len<=n; ++len) {
for (int i1=0; i1<=n-len; ++i1) {
for (int j2=0; j2<=n-len; ++j2) {
dp[len][i1][j2] = false;
for (int k=1; k<len; ++k) {
// 假设左半部分长度是k，dp[len][i][j] = dp[k][i][j] && dp[len-k][i+k][j+k].
// 也就是S1的左半部分和S2的左半部分匹配以及S1的右半部分和S2的右半部分匹配
// 假设左半部分长度是k，dp[len][i][j] = dp[k][i][j+len-k] && dp[len-k][i+k][j].
// 也就是S1的左半部分和S2的右半部分匹配以及S1的右半部分和S2的右半部分匹配
dp[len][i1][j2] = dp[len][i1][j2] || (dp[k][i1][j2] && dp[len-k][i1+k][j2+k]) || (dp[k][i1][j2+len-k] && dp[len-k][i1+k][j2]);
}
}
}
}
return dp[n][0][0];
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool isScramble(string s1, string s2) {
int s_len = s1.size(), len, i, j, k;
if (s_len == 0)
return true;
if (s_len == 1)
return (s1 == s2);
// Dynamic Programming
// 运行时决定数组长度：GCC4.8+ 和 Clang3.4+ 支持，非标准特性，属于扩展。
bool dp[s_len+1][s_len][s_len];
for(i=0; i<s_len; ++i)
for(j=0; j<s_len; ++j)
dp[1][i][j] = (s1[i] == s2[j]);
// dp[len][i][j]来表示s1[i, i+len)和s2[j, j+len)两个字符串是否满足条件.
// 换句话说，就是S1从i开始的len个字符是否能转换为S2从j开始的len个字符
for(len=2; len <=s_len; ++len) {
for(i=0; i<=s_len-len; ++i) {
for(j=0; j<=s_len-len; ++j) {
dp[len][i][j] = false;
for(k=1; k<len && !dp[len][i][j]; ++k) {
// 假设左半部分长度是k，dp[len][i][j] = dp[k][i][j] && dp[len-k][i+k][j+k].
// 也就是S1的左半部分和S2的左半部分匹配以及S1的右半部分和S2的右半部分匹配
// 假设左半部分长度是k，dp[len][i][j] = dp[k][i][j+len-k] && dp[len-k][i+k][j].
// 也就是S1的左半部分和S2的右半部分匹配以及S1的右半部分和S2的右半部分匹配
dp[len][i][j] = dp[len][i][j]
|| (dp[k][i][j] && dp[len-k][i+k][j+k])
|| (dp[k][i+len-k][j] && dp[len-k][i][j+k]);
}
}
}
}
return dp[s_len][0][0];
}
};