# [LintCode] 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 ifs2 is a scrambled string of s1.

Example

Challenge

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;
}
};

|
1月前
|
Java 索引
String字符串常用函数以及示例 JAVA基础
String字符串常用函数以及示例 JAVA基础
25 1
|
1月前
string（字符串）

21 3
|
2天前
|

【C++进阶】深入STL之string：模拟实现走进C++字符串的世界
【C++进阶】深入STL之string：模拟实现走进C++字符串的世界
|
3天前
|
C++ 容器
【C++语言】String 类关键函数实现，手搓一个简单字符串类！
【C++语言】String 类关键函数实现，手搓一个简单字符串类！
9 0
|
3天前
|
JSON Java 数据格式

10 1
|
9天前
|
Java 程序员 API
JavaSE——常用API（1/3）-包、String概述、String常用方法（length、charAt、遍历字符串、toCharArray......）
JavaSE——常用API（1/3）-包、String概述、String常用方法（length、charAt、遍历字符串、toCharArray......）v
8 0
|
13天前
|

【Redis】 String 字符串类型常见命令
【Redis】 String 字符串类型常见命令
14 1
|
15天前
|

【6月更文挑战第1天】🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，希望能够助你一臂之力，帮你早日登顶实现财富自由🚀；同时，欢迎大家关注&&收藏&&订阅！持续更新中，up！up！up！！
19 2
|
24天前
|

Redis -- String 字符串, 计数命令，字符串操作
Redis -- String 字符串, 计数命令，字符串操作
24 0
|
30天前
|

Java基础复习(DayThree)：字符串基础与StringBuffer、StringBuilder源码研究
Java基础复习(DayThree)：字符串基础与StringBuffer、StringBuilder源码研究
27 1