算法学习之动态规划(leetcode 87. Scramble String）

0x01题目

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":
           

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".
           

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".
           

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.
           

0x02解析

本题的目标是判断两个字符串之间的关系，正确的思路应该是使用遍历+分而治之的思想来做，若要判断两个字符串之间的关系，可以将两个字符串进行切割，判断切割后的子字符串之间的关系。

如果字符串s1[0, 1, … len-1]和s2[0, 1, …, len-1]满足scramble string条件（简称为SS条件），则有两种情况至少满足一种情况。

A. s1[0, 1, …i-1]和s2[0, 1, …i-1]满足SS条件且s1[i, len-1]和s2[i, len-1]满足SS条件

B. s1[0, 1, …i-1]和s2[len-i, len-1]满足SS条件且s1[i, len-1]和s2[0, 1, …len-i-1]满足SS条件

有两种解法：第一种递归，第二种动态规划，如代码所示。

0x03代码

解法一
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.equals(s2)) return true;
        if(s1.length() != s2.length()) return false;
        int len = s1.length();

        int[] letters = new int[];
        for(int i = ; i < len; i++){
            letters[s1.charAt(i) - 'a']++;
            letters[s2.charAt(i) - 'a']--;
        }

        for(int i = ; i < ; i++){
            if(letters[i] != ){
                return false;
            }
        }

        for(int i = ; i < len; i++){
            if(isScramble(s1.substring(, i), s2.substring(, i)) 
               &&
               isScramble(s1.substring(i), s2.substring(i))
               ){
                   return true;
               }
            if(isScramble(s1.substring(, i), s2.substring(len - i)) 
               &&
               isScramble(s1.substring(i), s2.substring(, len - i))
               ){
                   return true;
               }  
        }

        return false;
    }
}
           

解法二
/*
定义F(i, j, k)为S1[i..i + k - ]和S2[j..j + k - ]是否满足SS条件。
则需要遍历所有情况检查F(i, j, k)是否为真
S1 [   x1    |         x2         ]
i         i + q                i + k - 
有以下两种可能性    
S2 [   y1    |         y2         ]
j         j + q                j + k - 
或者
S2 [       y1        |     y2     ]
j                 j + k - q    j + k - 
所以，当 <= q < k时候，
F(i, j, k) = (
    F(i, j, q) AND F(i + q, j + q, k - q)) 
    OR 
    F(i, j + k - q, q) AND F(i + q, j, k - q)
    )
当k = 时
F(i, j, k) = (s1.charAt(i) == s2.charAt(j))；
*/
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int len = s1.length();

        boolean [][][] F = new boolean[len][len][len + ];
        for (int k = ; k <= len; ++k)
            for (int i = ; i + k <= len; ++i)
                for (int j = ; j + k <= len; ++j)
                    if (k == )
                        F[i][j][k] = (s1.charAt(i) == s2.charAt(j));
                    else for (int q = ; q < k && !F[i][j][k]; ++q) {
                        F[i][j][k] = (
                        F[i][j][q] && F[i + q][j + q][k - q]) 
                        || 
                        (F[i][j + k - q][q] && F[i + q][j][k - q]);
                    }
        return F[][][len];
    }
}