coder/ \co der/ \ / \c o d er/ \e r
ocder/ \oc der/ \ / \o c d er/ \e r
ocred / \ oc red / \ / \ o c re d / \ r e我们称"ocred"是"coder"的一个乱序字符串。
"ab","ab"
true
"ba","ab"
true
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1 == s2)
return true;
int c[26] = {0};
for(int i=0;i<s1.length();i++)
{
c[s1[i]-'a']++;
c[s2[i]-'a']--;
}
for(int i=0;i<26;i++)
if(c[i] != 0)
return false;
for(int i=1;i<s1.length();i++)
{
if(isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
return true;
if(isScramble(s1.substr(0,i), s2.substr(s2.length()-i)) && isScramble(s1.substr(i), s2.substr(0,s2.length()-i)))
return true;
}
return false;
}
}; 
/*
* 参考自leetcode网友：@baifriend
*/
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2))
return true;
int[] letters = new int[26];
for (int i = 0; i < s1.length(); i++) {
letters[s1.charAt(i) - 'a']++;
letters[s2.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++)
if (letters[i] != 0)
return false;
for (int i = 1; i < s1.length(); i++) {
if (isScramble(s1.substring(0, i), s2.substring(0, i))
&& isScramble(s1.substring(i), s2.substring(i)))
return true;
if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
&& isScramble(s1.substring(i), s2.substring(0, s2.length() - i)))
return true;
}
return false;
}
/*
* 思路：从简单情况开始，
* 1.两个字符串都只有一个字符时只需比较是否相等
* 2.字符个数大于一时，先判断长度是否相等，在判断是否由相同的字符组成，若否则直接返回false
* 3.分隔字符串，有两种情况，一种是不交换，一种是左右交换
*/
public class Solution {
public boolean isScramble(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 != len2)
return false;
if (len1 == 1)
return s1.equals(s2);
//剪枝:若排序后不不相等则必定不满足条件
char[] chars1 = new char[len1];
s1.getChars(0, len1, chars1, 0);
Arrays.sort(chars1);
char[] chars2 = new char[len1];
s2.getChars(0, len2, chars2, 0);
Arrays.sort(chars2);
if (!(new String(chars1).equals(new String(chars2))))
return false;
for (int i = 1; i < len1; i++) {
String s1left = s1.substring(0, i);
String s1right = s1.substring(i, len1);
String s2left = s2.substring(0, i);
String s2right = s2.substring(i, len1);
//在当前分割处没有交换
if (isScramble(s1left, s2left) && isScramble(s1right, s2right))
return true;
//当前分割处左右交换
s2right = s2.substring(len1 - i, len1);
s2left = s2.substring(0, len1 - i);
if (isScramble(s1left, s2right) && isScramble(s1right, s2left))
return true;
}
return false;
}
}
import java.util.*;
public class Solution {
/*
题意：求s2是不是s1的爬行字符串，其实就是s1任意交换字母，看能不能交换成s2
1、当s1，s2长度为1时，直接判断s1==s2即可获得答案
2、当s1为ab，那么s2只能ab或者ba
3、
例如：
3.1、gr|eat 和 rg|eat从第2个位置进行分割，不进行交换
a1=gr b1=eat a2=rg b2=eat
此时需要判断
(gr, rg) && (eat, eat)
3.2、对于 re|at 和 ta|er从第2个位置进行分割
a1=re b1=at a2=ta b2=er，这种显然这种是不符合的
那么s2的两部分交换，那么s'=er|ta
a1=re b1=at a2`=er b2`=ta，这种显然是符合条件的
对于任意长度的字符串，我们可以把字符串s1分为a1，b1两部，s2分为a2，b2两部分
满足 (a1~a2) && (b1~b2) || (a1~b2) && (a2~b1)
4、剪枝，判断两个字符串是否有相同的字符集，没有则直接剪去这个分支
*/
public boolean isScramble(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 != len2) {
return false;
}
if(len1 == 1) {
return s1.equals(s2);
}
char[] chs1 = s1.toCharArray();
char[] chs2 = s2.toCharArray();
Arrays.sort(chs1);
Arrays.sort(chs2);
String sortS1 = new String(chs1);
String sortS2 = new String(chs2);
if (!sortS1.equals(sortS2)) {
return false;
}
for(int i = 1; i < len1; i++) {
String s1Left = s1.substring(0, i);
String s1Right = s1.substring(i, len1);
String s2Left = s2.substring(0, i);
String s2Right = s2.substring(i, len1);
// 没有交换
if(isScramble(s1Left, s2Left) && isScramble(s1Right, s2Right)) {
return true;
}
// 交换比较
s2Right = s2.substring(len1 - i, len1);
s2Left = s2.substring(0, len1 - i);
if(isScramble(s1Left, s2Right) && isScramble(s1Right, s2Left)) {
return true;
}
}
return false;
}
}
/**
* 定义了一种爬行字符串，
* 假如把一个字符串当做一个二叉树的根，
* 然后它的非空子字符串是它的子节点，
* 然后交换某个子字符串的两个子节点，
* 重新爬行回去形成一个新的字符串，
* 这个新字符串和原来的字符串互为爬行字符串。
*
* 思路：递归
* 简单的说，就是s1和s2是scramble的话，
* 那么必然存在一个在s1上的长度l1，
* 将s1分成s11和s12两段，同样有s21和s22.
* 那么要么s11和s21是scramble的并且s12和s22是scramble的；
* 要么s11和s22是scramble的并且s12和s21是scramble的。
* 就拿题目中的例子 rgeat 和 great 来说，
* rgeat 可分成 rg 和 eat 两段，
* great 可分成 gr 和 eat 两段，
* rg 和 gr 是scrambled的， eat 和 eat 当然是scrambled。
*
* 摘自https://www.cnblogs.com/grandyang/p/4318500.html
**/
import java.util.Arrays;
public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
if (s1.equals(s2)) {
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
if (!Arrays.equals(c1, c2)) {
return false;
}
for (int i = 1; i < s1.length(); i++) {
if (isScramble(s1.substring(0, i), s2.substring(0, i))
&& isScramble(s1.substring(i), s2.substring(i))) {
return true;
}
if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
&& isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {
return true;
}
}
return false;
}
}
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1==s2) return true;
int A[26]={0};
for(int i=0;i<s1.length();++i){
A[s1[i]-'a']++;
A[s2[i]-'a']--;
}
for(int i=0;i<26;++i){
if(A[i]!=0) return false;
}
for(int i=1;i<s1.length();++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(s2.length()-i)) && isScramble(s1.substr(i),s2.substr(0,s2.length()-i))) return true;
}
return false;
}
}; }
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
bool isScramble(string s1, string s2);
};
bool Solution::isScramble(string s1, string s2) {
if (s1.size() != s2.size()) {
return false;
}
const int len = s1.length();
//DP[k][i][j] 表示s2的从j开始长度为k的子串是否为s1的从i开始长度为k的子串的scramble string
bool DP[len+1][len][len] = {false};
//初始化DP[1][i][j],长度为1的子串，只要相等就是scramble string
for (int i=0; i<len; ++i) {
for (int j=0; j<len; ++j) {
DP[1][i][j] = (s1[i]==s2[j]) ? true : false;
}
}
for (int k=2; k<=len; ++k) {
for (int i=0; i<=len-k; ++i) {
for (int j=0; j<=len-k; ++j) {
//div表示长度为k的子串中，将子串一分为二的分割点
for (int div=1; div<k && !DP[k][i][j]; ++div) {
// DP[k][i][j] = true的条件是子串分割后的两段对应相等，或者交叉对应相等
if ((DP[div][i][j]&&DP[k-div][i+div][j+div])
|| (DP[div][i][j+k-div]&&DP[k-div][i+div][j])) {
DP[k][i][j] = true;
}
}
}
}
}
return DP[len][0][0];
}
int main(int argc, char const *argv[]) {
string s1 = "tt";
string s2 = "tb";
Solution so;
bool res = so.isScramble(s1, s2);
return res;
}
//参考高票回答，思路简单，代码精简，忍不住描摹了一下
//使用数组计数实现s1,s2对应子树的字符串包含的字符是否相同，不同直接返回false
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1 == s2)
return true;
int c[26] = {0};
for(int i=0;i<s1.size();i++)
{
c[s1[i]-'a']++;
c[s2[i]-'a']--;
}
for(int j=0;j<26;j++)
{
if(c[j] != 0)
return false;
}
for(int k=1;k<s1.size();k++)
{
if(isScramble(s1.substr(0,k),s2.substr(0,k)) && isScramble(s1.substr(k),s2.substr(k)))
return true;
if(isScramble(s1.substr(0,k),s2.substr(s2.size()-k)) && isScramble(s1.substr(k),s2.substr(0,s2.size()-k)))
return true;
}
return false;
}
};
这样会很耗内存吗？ 通不过，求解答 bool isScramble(string s1, string s2) {
int n=s1.size();
if(n==1 && s1==s2)
return true;
if(n==1 && s1!=s2)
return false;
vector<string> res;
res.push_back(s1.substr(0,1));
for( int i = 0 ; i < n-1 ; i ++ )
{
int t = res.size();
for(int j=0; j < t ; j++)
{
string tmp=res[j];
//原有的不能保存在里面
res[j] = res[j]+s1[i+1];
res.push_back(s1[i+1]+tmp);
}
}
for(int j = 0; j < res.size(); j++)
{
cout<< res[j]<<endl;
if(s2==res[j])
return true;
}
return false;
}
import java.util.*;
public class Solution {
public boolean isScramble(String s1, String s2) {
if(s1.length() != s2.length()) return false;
if(s1.length() == 1 || s2.length() == 1) return s1.equals(s2);
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
for (int i = 0; i < arr1.length; i ++) {
if(arr1[i] != arr2[i]) return false;
}
for (int i = 1; i < s1.length(); i ++) {
String s1left = s1.substring(0, i);
String s1rigt = s1.substring(i);
String s2left = s2.substring(0, i);
String s2right = s2.substring(i);
if(isScramble(s1left, s2left) && isScramble(s1rigt, s2right)) return true;
s2left = s2.substring(0, s2.length() - i);
s2right = s2.substring(s2.length() - i);
if(isScramble(s1left, s2right) && isScramble(s1rigt, s2left)) return true;
}
return false;
}
}
牛客的标签里面有“动态规划”，搞得我一脸懵逼😳
本题应该用递归/贪心实现，条件如下：
代码如下：
//
// Created by jt on 2020/8/30.
//
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
/**
*
* @param s1 string字符串
* @param s2 string字符串
* @return bool布尔型
*/
bool isScramble(string s1, string s2) {
// write code here
return dfs(s1, s2);
}
bool dfs(string s1, string s2) {
if (s1.size() != s2.size()) return false;
if (s1 == s2) return true;
unordered_map<char, int> um;
for (int i = 0; i < s1.size(); ++i) {
++um[s1[i]]; --um[s2[i]];
}
for (auto it = um.begin(); it != um.end(); ++it) {
if (it->second != 0) return false;
}
for (int i = 1; i < s1.size(); ++i) {
if (dfs(s1.substr(0, i), s2.substr(0, i)) &&
dfs(s1.substr(i), s2.substr(i))) return true;
if (dfs(s1.substr(0, i), s2.substr(s1.size()-i)) &&
dfs(s1.substr(i), s2.substr(0, s1.size()-i))) return true;
}
return false;
}
};
class Solution:
def isScramble(self , s1 , s2 ):
# write code here
if s1 == s2:
return True
if len(s1) != len(s2):
return False
chars = [0]*26 # 判断是否字符串的字母都一样
l = len(s2)
for i in range(l):
chars[ord(s1[i])-ord('a')] += 1
chars[ord(s2[i])-ord('a')] -= 1
for i in chars:
if i != 0:
return False
for i in range(1,l): # 从1开始
if self.isScramble(s1[:i], s2[:i]) & self.isScramble(s1[i:],s2[i:]):
return True
if self.isScramble(s1[:i], s2[-i:]) & self.isScramble(s1[i:],s2[:-i]): #对调
return True
return False 
/*
* 目的：乱序字符串
* 方法：参考大佬的
* 1.两个字符串都只有一个字符时只需比较是否相等
* 2.字符个数大于一时，先判断长度是否相等，在判断是否由相同的字符组成，若否则直接返回false
* 3.分隔字符串，有两种情况，一种是不交换，一种是左右交换
*/
bool isValid(string s1, string s2){
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
return s1==s2;
}
bool isScramble(string s1, string s2) {
if (s1.size()!=s2.size())
return false;
if (s1.empty() || s1==s2)
return true;
if (!isValid(s1,s2)){
return false;
}
for (int i = 1;i<s1.size();++i){
string left = s1.substr(0,i);
string right = s1.substr(i,s1.size()-i);
if (isScramble(left,s2.substr(0,i))&&
isScramble(right,s2.substr(i,s2.size()-i)))
return true;
if (isScramble(right,s2.substr(0,right.size()))&
&isScramble(left,s2.substr(right.size(),i)))
return true;
}
return false;
}
//扰乱字符串可以分成两部分进行递归，第一个部分A，第二部分B，A和B分别时对应子串的扰乱字符串
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size())
return false;
if(s1.size()==0||s1==s2)
return true;
string ss1=s1,ss2=s2;
sort(ss1.begin(),ss1.end());
sort(ss2.begin(),ss2.end());
if(ss1!=ss2)
return false;
//将s2字符串切分为前i个字符和后s2.size()-i个字符
for(int i=1;i<s2.size();i++){
//s1前i个字符和s2前i个字符配对
//s1前i个字符和s2后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(s2.size()-i))&&
isScramble(s1.substr(i), s2.substr(0,s2.size()-i))))
return true;
}
return false;
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
