链接：LintCode 炼码 - 更高效的学习体验！

题解：

LintCode 炼码 - 更高效的学习体验！

class Solution { public: /** * @param s1: A string * @param s2: Another string * @return: whether s2 is a scrambled string of s1 */ bool isScramble(string &s1, string &s2) { // write your code here int m = s1.size(); int n = s2.size(); if (m != n) { return false; } std::vector<std::vector<std::vector<int>>> dp(m+1, std::vector<std::vector<int>>(n+1, std::vector<int>(n+1, -1))); // s1从i开始，s2从j开始，长度为m，是否可以构成 return dfs(0, 0, m, s1, s2, dp); return dp[0][0][m] == 1 ? true : false; } private: bool dfs(int b1, int b2, int len, string &s1, string &s2, std::vector<std::vector<std::vector<int>>>&dp) { if (len == 1) { dp[b1][b2][1] = s1[b1] == s2[b2] ? 1 : 0; return dp[b1][b2][1] == 1 ? true : false; } if (dp[b1][b2][len] != -1) { return dp[b1][b2][len]; } for (int i = 1; i < len; ++i) { if (dfs(b1, b2, i, s1, s2, dp) && dfs(b1+i, b2+i, len-i, s1, s2, dp)) { dp[b1][b2][len] = 1; return true; } if (dfs(b1+len-i, b2, i, s1, s2, dp) && dfs(b1, b2+i, len-i, s1, s2, dp)) { dp[b1][b2][len] = 1; return true; } } dp[b1][b2][len] = 0; return false; } };

class Solution { public: /** * @param s1: A string * @param s2: Another string * @return: whether s2 is a scrambled string of s1 */ bool isScramble(string& s1, string& s2) { // write your code here int m = s1.size(); int n = s2.size(); if (m != n) { return false; } if (m <= 0) { return true; } vector<vector<bool>> tmp(n, vector<bool>(n + 1, false)); vector<vector<vector<bool>>> dp(m, tmp); // 初始化长度 1 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { dp[i][j][1] = (s1[i] == s2[j]); } } for (int len = 1; len <= m; ++len) { for (int i = 0; i + len - 1 < m; ++i) { for (int j = 0; j + len - 1 < n; ++j) { for (int k = 1; k <= len - 1; ++k) { if (dp[i][j][k] && dp[i + k][j + k][len - k]) { dp[i][j][len] = true; break; } } for (int k = 1; k <= len - 1; ++k) { if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) { dp[i][j][len] = true; break; } } } } } return dp[0][0][m]; } };

第一唯是枚举长度len

dp[i][j][len] 从i和j位置分别开始，长度为len的情况下是否能构成

初始化dp[i][j][1] 时候，判断s1[i] == s2[j]