最先看到这一题，直觉的解法就是len从1到s1.size()-1，递归调用比較s1和s2长度为len的子串是否相等。以及剩余部分是否相等。

将s1分成s1[len + rest]，分别比較s2[len + rest]和s2[rest + len]

代码例如以下：

    bool isScramble(string s1, string s2) {

		return find(s1, s2);

    }

	bool find(string s1, string s2) {

		if (s1.compare(s2) == 0) return true;

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

		{

			if (find(s1.substr(0, i), s2.substr(0,i)) && find(s1.substr(i), s2.substr(i)))

				return true;

			if (find(s1.substr(0, i), s2.substr(s2.size() - i)) && find(s1.substr(i), s2.substr(0, s2.size() - i)))

				return true;

		}

		return false;

    }

是一个TLE的算法

改进点1：在find中查看s1和s2是否字母同样，假设不同。返回false

代码例如以下：

    bool isScramble(string s1, string s2) {

		return find(s1, s2);

    }

	bool find(string s1, string s2) {

		if (!haveSameChar(s1, s2)) return false;

		if (s1.compare(s2) == 0) return true;

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

		{

			if (find(s1.substr(0, i), s2.substr(0,i)) && find(s1.substr(i), s2.substr(i)))

				return true;

			if (find(s1.substr(0, i), s2.substr(s2.size() - i)) && find(s1.substr(i), s2.substr(0, s2.size() - i)))

				return true;

		}

		return false;

    }

	bool haveSameChar(string& s1, string& s2)

	{

		int chars[26] = {0};

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

		{

			chars[s1[i] - 'a'] ++;

		}

		for (int i = 0; i < s2.size(); i++)

		{

			if (chars[s2[i] - 'a'] == 0)  return false;

			chars[s2[i] - 'a'] --;

		}

		return true;

	}

改进点2：存储状态，将问题转换为三维DP

dp(i, j, l)：s1[i...i+l]和s2[j...j+l]是否满足要求

dp(i, j, l) = dp(i, j, k) && dp(i + k, j + k, l - k) || dp(i, j + l - k, k) && dp(i + k, j, l - k)

    vector<vector<vector<int>>> dp;

    bool isScramble(string s1, string s2) {

        int size = s1.size();

        dp = vector<vector<vector<int>> > (size, vector<vector<int>>(size, vector<int>(size + 1)));

        return find(s1, s2, 0, 0, size);

    }

    bool find(string & s1, string & s2, int l1, int l2, int length)

    {

        if (dp[l1][l2][length] != 0)

            return dp[l1][l2][length] == 1;

        dp[l1][l2][length] = -1;

        if (length == 1)

            dp[l1][l2][length] = ((s1[l1] == s2[l2]) ? 1 : -1);

        for (int len = 1; len < length; len++)

        {

            if (find(s1, s2, l1, l2, len) && find(s1, s2, l1 + len, l2 + len, length - len))

            {

                dp[l1][l2][length] = 1;

                break;

            }

            if (find(s1, s2, l1, l2 + length - len, len) && find(s1, s2, l1 + len, l2, length - len))

            {

                dp[l1][l2][length] = 1;

                break;

            }

        }

        return dp[l1][l2][length] == 1;

    }