聖地亞歌

Leetcode P0087"Scramble String" 题解

2020/08/31 Leetcode

博文中会简要介绍Leetcode P0087题目分析及解题思路。

“Scramble String”是一道比较难的动态规划题目，这道题的难点在于寻找最优子结构。这道题最终是一个高维动态规划，寻找最优子结构相对而言比较难，反而是最终的递推式逻辑简单，并不复杂。

We can scramble a string s to get a string t using the following algorithm:

  1. If the length of the string is 1, stop.
  2. 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];
    }
}
Java

以下是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];            
    }
};
C++

Search