LeetCode: Scramble String

思路分析

首先，这是个三维DP，不要上来傻乎乎敲朴素搜索，标记为Hard的题目自然是有一定难度的。如果是Onsite遇到这类问题，思路明显错误的话，我想面试官应该会给出一定的提示。

回到正题。先考虑怎样记录状态，对于这个问题，显然应该有dp[i][j][k]表示s1.substr(i, k)与s2.substr(j, k)能否构成“Scramble String”，而答案应该就是dp[0][0][length]。还是使用传统的左闭右开区间可以使得问题的表述非常清晰，于是接下来考虑如何进行状态转移。

如果DP思路清晰的话，可以直接写出一个四重循环递推。优点是一眼就能看出复杂度为O(n^4)，而缺点则是不大好想，对于DP没有经验的话边界细节、递推顺序很容易弄错。对于我这样的DP渣渣，就直接上记忆化搜索的写法了，优点是优雅好写，但是复杂度常数就要大很多。但是总而言之，一切DP都可以用记忆化搜索来表达。

记忆化搜索的思想是，对于任何一个被搜索的状态DFS(i,j,len)，枚举一个切分位置k，只要满足DFS(i,j,k)&&DFS(i+k,j+k,len-k)||DFS(i,j+len-k,k)&&DFS(i+k,j,len-k)为真，那么该状态就是为真的。这个表达式的意思是，我们将s1中从i起始长度为len的字符串从k处切分成长度为k和len-k的两段，对s2也做同样的操作，如果存在“前前后后”或者“前后后前”的匹配方式，则说明可以构成“Scramble String”，否则就不可以。仔细观察字符串的构造方式，就可以发现这个表达式的含义是显然的。

代码

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
const int MAX = 110;
int dp[MAX][MAX][MAX];

class Solution {
public:
    bool isScramble(string s1, string s2) {
        CLR(dp, -1);
        int len = s1.length();
        rep(i, len)
        rep(j, len) {
            dp[i][j][1] = ( s1[i] == s2[j] );
        }
        return bool(DFS(0, 0, len));
    }
    int DFS( int i, int j, int len )
    {
        if ( dp[i][j][len] != -1 ) return dp[i][j][len];
        int ans = 0;
        //枚举拆分位置
        REP(k, 1, len) {
            if ( ( DFS(i, j, k) && DFS(i + k, j + k, len - k) ) ||\
                 ( DFS(i, j + len - k, k) && DFS(i + k, j, len - k) ) ) {
                    ans = 1;
                    break;
                 }
        }
        return dp[i][j][len] = ans;
    }
};