## 题目地址

https://leetcode.com/problems/scramble-string/

## 题目描述

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 if s2 is a scrambled string of s1.

Example 1:

``````Input: s1 = "great", s2 = "rgeat"
Output: true
``````

Example 2:

``````Input: s1 = "abcde", s2 = "caebd"
Output: false
``````

## 代码

``````// Recursion
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[i][j][len] = || (dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k] && dp[i+k][j][len-k])

``````// 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)));
for (int len = 1; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
for (int j = 0; j <= n - len; ++j) {
if (len == 1) {
dp[i][j][1] = s1[i] == s2[j];
} else {
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];
}
};
``````

``````     r    g    e
g    x    √    x
r    √    x    x
e    x    x    √

rg    ge
gr    √    x
re    x    x

rge
gre   √
``````

DP 的另一种写法，参考网友加载中..的博客，思路都一样，代码如下：

``````// Still 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)));
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:
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) {
if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) || (isScramble(s1.substr(0, i), s2.substr(n - i)) && isScramble(s1.substr(i), s2.substr(0, n - i)))) {
return true;
}
}
return false;
}
};
``````

``````class Solution {
public:
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<int>>> memo(n, vector<vector<int>>(n, vector<int>(n + 1, -1)));
return helper(s1, s2, 0, 0, n, memo);
}
bool helper(string& s1, string& s2, int idx1, int idx2, int len, vector<vector<vector<int>>>& memo) {
if (len == 0) return true;
if (len == 1) memo[idx1][idx2][len] = s1[idx1] == s2[idx2];
if (memo[idx1][idx2][len] != -1) return memo[idx1][idx2][len];
for (int k = 1; k < len; ++k) {
if ((helper(s1, s2, idx1, idx2, k, memo) && helper(s1, s2, idx1 + k, idx2 + k, len - k, memo)) || (helper(s1, s2, idx1, idx2 + len - k, k, memo) && helper(s1, s2, idx1 + k, idx2, len - k, memo))) {
return memo[idx1][idx2][len] = 1;
}
}
return memo[idx1][idx2][len] = 0;
}
};
``````

评论
0 评论