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.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

题目分析以及解决思路

题目的意思也比较明确吧，给出两个字符串，将字符串分割成一个二叉树，并且可以交换非叶子节点，求解两个字符串能否相互构造。

方法 1 - `递归`

思路：将字符串划分为两部分，分别递归得到结果是否scramble。需要考虑完备性，即需要将各种划分情况都需要考虑一遍。
- 情况①： s1的前k个字符与s2的前k个字符进行判断同时 s1的后size-k个字符与s2的后size-k进行判断 — isScramble(s1.substr(0, k), s2.substr(0, k)) && isScramble(s1.substr(k, size-k), s2.substr(k, size-k))
- 情况②： s1的前k个字符与s2的后k个字符进行判断同时 s1的后size-k个字符与s2的前size-k进行判断 — isScramble(s1.substr(0, size-k), s2.substr(k, size-k)) && isScramble(s1.substr(size-k, k), s2.substr(0, k))

实现代码：

如果不剪枝将会造成超时

// 递归

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1 == s2)	return true;
        if(s1.size() != s2.size())	return false;

        int size = s1.size();

        // 剪枝
        int letter[26] = {0};
        for(int i = 0; i < size; ++i) {
            letter[s1[i] - 'a'] ++;
            letter[s2[i] - 'a'] --;
        }
        for(int i = 0; i < 26; ++i) {
            if(letter[i] > 0)
                return false;
        }

        for(int k = 1; k < size; ++k) {
            if(isScramble(s1.substr(0, k), s2.substr(0, k)) && isScramble(s1.substr(k, size-k), s2.substr(k, size-k)))
                return true;
            if(isScramble(s1.substr(0, size-k), s2.substr(k, size-k)) && isScramble(s1.substr(size-k, k), s2.substr(0, k)))
                return true;
        }
        return false;
    }
};

方法 2 - `动态规划`

我们需要维护一个变量match[i][j][n]，其中i为字符串s1的起始字符，j为字符串s2的起始字符，n为当前字符的长度，match[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。
如何得到match[i][j][n]，推导出其中的状态转移方程，其实与递归中的思路相同。我们对于当前情况，需要对于目前所有可能的划分都去检索一次，如果有一次划分是scramble的，则match[i][j][len]即为true，倘若所有的划分都不是scramble的，则match[i][j][len]即为false。关于划分，同时需要划分两种情况：
- 情况①： s1以i为起始的前k个字符与s2以j为起始的前k个字符进行判断同时 s1的后len-k个字符与s2的后len-k进行判断 — match[i][j][k] && match[i+k][j+k][len-k]
- 情况②： s1以i为起始的k个字符与s2以j+len-k为起始的k个字符进行判断同时 s1以i+k为起始的len-k个字符与s2以j为起始的len-k进行判断 — match[i][j+len-k][k] && match[i+k][j][len-k]

实现代码：

// dp

class Solution {
public:
    bool isScramble(string s1, string s2) {

        if(s1.size() != s2.size())	return false;

        if(!s1.size())	return true;

        int size = s1.size();
        // s1_start, s2_start, match_len
        bool match[size][size][size+1];

        for(int i = 0; i < size; ++i)
            for(int j = 0; j < size; ++j)
                match[i][j][1] = (s1[i] == s2[j]);

        for(int len = 2; len <= size; ++len) 
            for(int i = 0; i <= size - len; ++i) 
                for(int j = 0; j <= size - len; ++j) {
                    match[i][j][len] = false;	// initial
                    for(int k = 1; k < len; ++k) 
                        match[i][j][len] |= (match[i][j][k] && match[i+k][j+k][len-k]) \
                                            || (match[i][j+len-k][k] && match[i+k][j][len-k]); 			
                }

        return match[0][0][size];
    }
};

题目

题目分析以及解决思路

方法 1 - 递归

方法 2 - 动态规划

方法 1 - `递归`

方法 2 - `动态规划`