题目

scramble-string

算法

* 递归

• 简单的说，就是s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12两段，同样有s21和s22.那么要么s11和s21是scramble的并且s12和s22是scramble的；要么s11和s22是scramble的并且s12和s21是scramble的。就拿题目中的例子 rgeat 和 great 来说，rgeat 可分成 rg 和 eat 两段， great 可分成 gr 和 eat 两段，rg 和 gr 是scrambled的， eat 和 eat 当然是scrambled。

* DP

http://www.cnblogs.com/grandyang/p/4318500.html

• O（n）：三维DP

代码

* 递归

class Solution {

public:

    bool isScramble(string s1, string s2) {

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

        if (s1 == s2) return true;

        string str1 = s1, str2 = s2;

        sort(str1.begin(), str1.end());

        sort(str2.begin(), str2.end());

        if (str1 != str2) return false;

        for (int i = 1; i < s1.size(); ++i) {

            string s11 = s1.substr(0, i);

            string s12 = s1.substr(i);

            string s21 = s2.substr(0, i);

            string s22 = s2.substr(i);

            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;

            s21 = s2.substr(s1.size() - i);

            s22 = s2.substr(0, s1.size() - i);

            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;

        }

        return false;

    }

};

* DP

class Solution {

public:

    bool isScramble(string s1, string s2) {

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

        if (s1 == s2) return true;

        int n = s1.size();

        vector<vector<vector<bool> > > dp (n, vector<vector<bool> >(n, vector<bool>(n + 1, false)));

        for (int i = 0; i < n; ++i) {

            for (int j = 0; j < n; ++j) {

                dp[i][j][1] = s1[i] == s2[j];

            }

        }

        for (int len = 2; len <= n; ++len) {

            for (int i = 0; i <= n - len; ++i) {

                for (int j = 0; j <= n - len; ++j) {

                    for (int k = 1; k < len; ++k) {

                        if ((dp[i][j][k] && dp[i + k][j + k][len - k]) || (dp[i + k][j][len - k] && dp[i][j + len - k][k])) {

                            dp[i][j][len] = true;

                        }

                    }

                }

            }

        }

        return dp[0][0][n];

    }

};