链接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::vectorstd::vectorstd::vectorint dp(m1, std::vectorstd::vectorint(n1, std::vectorint(n1, -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::vectorstd::vectorstd::vectorintdp) { 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(b1i, b2i, len-i, s1, s2, dp)) { dp[b1][b2][len] 1; return true; } if (dfs(b1len-i, b2, i, s1, s2, dp) dfs(b1, b2i, 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; } vectorvectorbool tmp(n, vectorbool(n 1, false)); vectorvectorvectorbool 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]; } };第一唯是枚举长度lendp[i][j][len] 从i和j位置分别开始长度为len的情况下是否能构成初始化dp[i][j][1] 时候判断s1[i] s2[j]