算法设计与分析--动态规划（十）
Scramble String
更多技术博客 http://vilins.top/
题目
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.
Example 1:
Input: s1 = “great”, s2 = “rgeat”
Output: true
Example 2:
Input: s1 = “abcde”, s2 = “caebd”
Output: false
分析
法一：
从题目给出的定义来看，该过程是通过树来定义的，而树是通过递归进行定义的，那么我们可以大胆地猜测，这个过程可以通过递归的方式去解决。在完成验证之前，我们需要对一些简单的情况进行排除：
- 长度不一样的直接排除。
- 相同的字母个数不一样的直接排除。
- 通过递归的方式对其进行验证。
在用递归进行处理的时候，我们需要注意可能出现的情况，首先是根节点下的两个节点直接做了交换，这种情况，我们验证的时候需要将源字符的前半段和目标字符的后半段对比，然后递归地进行比较。也就是
(isScramble(s1.substr(0, i), s2.substr(size - i, i))&&isScramble(s2.substr(0, size - i), s1.substr(i, size-i)))另外一种情况是根节点下属的两个没有进行直接的交换，这时字符串的前半段是在前半段进行交换，后半段在后半段的范围内进行交换，情况如下：
isScramble(s1.substr(0, i), s2.substr(0, i))&&isScramble(s1.substr(i), s2.substr(i))这两种情况有一种情况成立，我们就认为这个交换是合法的。
法二：
这里我们选择用动态规划思想去解决，定义dp[i][j][len]表示第一个字符串下标i开始，第二个字符串下标j开始的长度为len并且这个交换是合法的字串，那么最后结果的表示就是dp[0][0][size]，那么我们求出其子问题即可，首先我们将两个字符串字符相等的对dp进行初始化，然后我们寻找状态转移方程，对应一个dp[i][j][len]是否合法，我们有一下三种情况：
- dp[i][j][len]这个问题已经求过并且它是合法的。
- 将这个问题划分，如果是没有进行前后交换的情况，有如下状态转移方程：
dp[i][j][len] = (dp[i][j][k]&&dp[i+k][j+k][len-k])- 如果有进行前后交换的情况，状态转移方程如下：
dp[i][j][len] = (dp[i][j+len-k][k]&&dp[i+k][j][len-k])综合起来，总的状态转移方程就是：
dp[i][j][len] = dp[i][j][len] || (dp[i][j][k]&&dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k]&&dp[i+k][j][len-k]);源码
递归实现
class Solution { public: bool isScramble(string s1, string s2) { if(s1 == s2) { return true; } //first base test if(s1.size() != s2.size()) { return false; } vector<int> count1(26, 0); vector<int> count2(26, 0); for(int i = 0; i < s1.size(); i++) { count1[s1[i] - 'a']++; count2[s2[i] - 'a']++; } for(int i = 0; i < 26; i++) { if(count1[i] != count2[i]) { return false; } } int size = s1.size(); for(int i = 1; i < s1.size(); i++) { if(isScramble(s1.substr(0, i), s2.substr(0, i))&&isScramble(s1.substr(i), s2.substr(i)) || (isScramble(s1.substr(0, i), s2.substr(size - i, i))&&isScramble(s2.substr(0, size - i), s1.substr(i, size-i)))) { return true; } } return false; } };动态规划实现
class Solution { public: bool isScramble(string s1, string s2) { if(s1.size() == 0) { return true; } vector<vector<vector<bool>>> dp(s1.size(), vector<vector<bool>>(s2.size(), vector<bool>(s1.size()+1, false))); for(int i = 0; i < s1.size(); i++) { for(int j = 0; j < s2.size(); j++) { if(s1[i] == s2[j]) { dp[i][j][1] = true; } } } for(int len = 2; len <= s1.size(); len++) { for(int i = 0; i < s1.size() - len + 1; i++) { for(int j = 0; j < s2.size() - len + 1; j++) { for(int k = 1; k < len; k++) { dp[i][j][len] = dp[i][j][len] || (dp[i][j][k]&&dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k]&&dp[i+k][j][len-k]); } } } } return dp[0][0][s1.size()]; } };