搅乱字符串

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

牛客的标签里面有“动态规划”，搞得我一脸懵逼😳

本题应该用递归/贪心实现，条件如下：

1. 基准1: 如果两个字符串长度不相等，返回false
2. 基准2: 如果两个字符串相等，返回false
3. 基准3: 如果两个字符串中对应字符的个数不相等，返回false
4. 递归判断子字符串是否是乱序字符串

代码如下：

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