加擾字符串


難度級別
經常問 亞馬遜 狂徒 Samsung
分而治之 動態編程

問題陳述

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

解釋

令字符串s =“ great”

代表 s 通過將其遞歸地分為兩個非空子字符串將其作為二叉樹。

加擾字符串

可以通過選擇任何非葉節點並交換其子節點來加擾該字符串。

加擾字符串

因此,“ rgeat”是原始字符串的加擾字符串,即“ great”。

s1 = "great"

s2 = "rgeat"
Yes

說明:如上圖所示,我們可以看到擾亂“ great”結果為“ great”。 因此結果是“是”。

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的空格。