# 加擾字符串

## 問題陳述

“加擾字符串”問題指出您得到了兩個字符串。 檢查第二 是第一個的加擾字符串嗎？

## 例

```s1 = "great"

s2 = "rgeat"```
`Yes`

```s1 = "abcde"

s2 = "caebd"```
`No`

## 加擾字符串問題的算法

```1. Initialize the two string variables s1 and s2 of the same size.
2. Create a function to check is the second string is the scrambled string of first string which accepts two string variables as it's a parameter.
3. Check if the first string is equal to the second string, return true.
4. After that, sort the first string using the inbuilt sort function.
5. Similarly, sort the second string using the inbuilt sort function.
6. Check again if the first string is not equal to the second string, return false.
7. Else create a variable scramble of the boolean type and initialize it as false.
8. After that, traverse from 0 to the length of the string and make a recursive call to the function itself for all the possible index combinations of the first string and the second string and store the result of the recursive calls in the boolean variable scramble.
9. Finally, check If the value of the boolean variable scramble is equal to the true then print "Yes".
10. Else if the value of the boolean variable scramble is equal to the false then print "No".```

## 推薦碼

### C ++程序檢查加擾字符串

```#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool isAnagram( string s1, string s2 ){
sort( s1.begin(), s1.end() );
sort( s2.begin(), s2.end() );
if( s1 != s2 )
return false;
else
return true;
}

bool isScramble(string s1, string s2){
if( s1 == s2 )
return true;

if( !isAnagram( s1, s2 ) )
return false;

bool scramble = false;
int length = s1.length();
for( int i = 1; i < length; i++ ){
scramble = scramble ||
( isScramble( s1.substr( 0, i ), s2.substr( 0, i ) ) &&
isScramble( s1.substr( i, length - i ), s2.substr( i, length - i ) ) )||
( isScramble( s1.substr( 0, i ), s2.substr( length - i, i ) ) &&
isScramble( s1.substr( i, length - i ), s2.substr( 0, length - i ) ) );
}
return scramble;
}

int main(){
string s1 = "great";
string s2 = "rgeat";
if(isScramble(s1,s2)){
cout<<"Yes";
}
else{
cout<<"No";
}
return 0;
}```
`Yes`

### Java程序檢查加擾字符串

```import java.util.*;

class Scramble{

static boolean isScramble(String s1, String s2){

if(s1.length()!=s2.length())
return false;

if(s1.length()==0 || s1.equals(s2))
return true;

char[] a1 = s1.toCharArray();
char[] a2 = s2.toCharArray();

Arrays.sort(a1);
Arrays.sort(a2);

if(!new String(a1).equals(new String(a2))){
return false;
}

for(int i=1; i<s1.length(); i++){
String s11 = s1.substring(0, i);
String s12 = s1.substring(i, s1.length());
String s21 = s2.substring(0, i);
String s22 = s2.substring(i, s2.length());
String s23 = s2.substring(0, s2.length()-i);
String s24 = s2.substring(s2.length()-i, s2.length());

if(isScramble(s11, s21) && isScramble(s12, s22))
return true;
if(isScramble(s11, s24) && isScramble(s12, s23))
return true;
}

return false;
}

public static void main (String[] args){
String s1 = "great";
String s2 = "rgeat";
if(isScramble(s1,s2)){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
```
`Yes`

## 複雜度分析

### 時間複雜度

O（2 ^ n） 其中n是第一個字符串或第二個字符串中的字符數。

### 空間複雜度

O（2 ^ n） 因為我們在程序的第一和第二個字符串的字符中使用了2 ^ n的空格。