LeetCode: 87. 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.

题目大意: 将字符串 s1 表示成某种二叉树, 然后多次交换某个非叶节点的子节点生成 s2， 则称 s2 是 s1 的 scrambled string。 给定俩长度相等的字符串 s1, s2，判断 s2 是否是 s1 的 scrambled string。

解题思路 —— 动态规划

• 令 dp[i][j][size] 表示 s2.substr(j, size) 是否是 s1.substr(i, size) 的 scrambled string;
• 如果 size = 0, 则 s2 一定是 s1 的 scrambled string。即: dp[i][j][0] = true;
• 如果 size = 1, 则当 s1[i](s1.substr(i, 1)) 等于 s2[j](s2.substr(j, 1)) 时， s2 才是 s1 的 scrambled string;
• 否则, 若以下一条成立，则s2 一定是 s1 的 scrambled string：
  
  • s1 可能被拆分成 s1.substr(i, size-k) 和 s1.substr(i+size-k, k) 两段(两个子树), 然后交换位置形成 s2.substr(j, size)(如图)。 那么: dp[i][j][size] = (dp[i][j+k][size-k] && dp[i+size-k][j][k]);
    
  • s1 可能被拆分成 s1.substr(i, k) 和 s1.substr(i+k, size-k) 两段(两个子树), 然后分别对两段(两棵子树)进行可能的操作(如图)。 那么: dp[i][j][size] = (dp[i][j][k] && dp[i+k][j+k][size-k]);
    

AC 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        const static int MAXN = 100;

        // 令 `dp[i][j][size]` 表示 `s2.substr(j, size)` 是否是 `s1.substr(i, size)`  的 scrambled string
        bool dp[MAXN][MAXN][MAXN];

        // initializing...
        for(int i = 0; i < s1.size(); ++i)
        {
            for(int j = 0; j < s2.size(); ++j)
            {
                // 如果 `size = 0`, 则 `s2` 一定是 `s1` 的 scrambled string
                dp[i][j][0] = true;

                // 如果 `size = 1`, 则当 `s1[i]`(`s1.substr(i, 1)`) 等于 `s2[j]`(`s2.substr(j, 1)`) 时，
                // `s2` 才是 `s1` 的 scrambled string.
                dp[i][j][1] = (s1[i] == s2[j]);
            }
        }


        for(int size = 2; size <= s1.size(); ++size)
        {
            for(int i = 0; i <= s1.size() - size; ++i)
            {
                for(int j = 0; j <= s2.size() - size; ++j)
                {  
                    dp[i][j][size] = false;

                    for(int k = 1; k < size; ++k)
                    {
                        // `s1` 可能被拆分成 `s1.substr(i, size-k)` 和 `s1.substr(i+size-k, k)`  两段(两个子树),
                        // 然后交换位置形成 `s2.substr(j, size)`                         if(dp[i][j+k][size-k] && dp[i+size-k][j][k])
                        {
                            dp[i][j][size] = true;
                            break;
                        }

                        // `s1` 可能被拆分成 `s1.substr(i, k)` 和 `s1.substr(i+k, size-k)`  两段(两个子树),
                        // 然后分别对两段(两棵子树)进行可能的操作。
                        if(dp[i][j][k] && dp[i+k][j+k][size-k])
                        {
                            dp[i][j][size] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][s1.size()];
    }
};