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":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
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".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
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".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine ifs2 is a scrambled string of s1.
O(n3) time
LeetCode上的原题，请参见我之前的博客Scramble String。
解法一：
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) { if (s1 == s2) return true; if (s1.size() != s2.size()) return false; string t1 = s1, t2 = s2; sort(t1.begin(), t1.end()); sort(t2.begin(), t2.end()); if (t1 != t2) return false; int n = s1.size(); for (int i = 1; i < s1.size(); ++i) { string a1 = s1.substr(0, i), b1 = s1.substr(i), a2 = s2.substr(0, i), b2 = s2.substr(i); string a3 = s2.substr(n - i), b3 = s2.substr(0, n - i); if ((isScramble(a1, a2) && isScramble(b1, b2)) || (isScramble(a1, a3) && isScramble(b1, b3))) { return true; } } 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) { if (s1 == s2) return true; if (s1.size() != s2.size()) return false; int n = s1.size(); vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(n + 1, false))); for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { for (int k = 1; k <= n - max(i, j); ++k) { if (s1.substr(i, k) == s2.substr(j, k)) { dp[i][j][k] = true; } else { for (int t = 1; t < k; ++t) { if ((dp[i][j][t] && dp[i + t][j + t][k - t]) || (dp[i][j + k - t][t] && dp[i + t][j][k - t])) { dp[i][j][k] = true; break; } } } } } } return dp[0][0][n]; } };
解法三：
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) { if (s1 == s2) return true; if (s1.size() != s2.size()) return false; int n = s1.size(), m[26] = {0}; for (int i = 0; i < n; ++i) { ++m[s1[i] - 'a']; --m[s2[i] - 'a']; } for (int i = 0; i < 26; ++i) { if (m[i] != 0) return false; } for (int i = 1; i < n; ++i) { string a1 = s1.substr(0, i), b1 = s1.substr(i); string a2 = s2.substr(0, i), b2 = s2.substr(i), a3 = s2.substr(n - i), b3 = s2.substr(0, n - i); if ((isScramble(a1, a2) && isScramble(b1, b2)) || (isScramble(a1, a3) && isScramble(b1, b3))) { return true; } } return false; } };
本文转自博客园Grandyang的博客，原文链接：爬行字符串[LintCode] Scramble String ，如需转载请自行联系原博主。
