Сцрамбле Стринг  


Ниво тешкоће Средњи
Често питани у амазонка Фанатици самсунг
Завади па владај Динамичко програмирање низ Дрво

Изјава о проблему  

Проблем „Сцрамбле Стринг“ наводи да су вам дате две жице. Провери да ли је други низ да ли је кодирани низ првог или није?

Објашњење

Нека је стринг с = „сјајно“

Заступљеност s као бинарно стабло рекурзивним дељењем на два непразна подниза.

Сцрамбле Стринг

Овај низ се може кодирати одабиром било којег чвора који није лист и заменом његове деце.

Сцрамбле Стринг

Стога је „ргеат“ кодирани низ изворног низа, тј. „Сјајан“.

Пример  

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".

за решавање овог проблема, пре свега, покушавамо да проверимо неколико ствари. Прва ствар коју проверавамо је да ли су оба низа једнака или не. Под једнаким, овде подразумевамо да су знакови у свим индексима низа исти или не. Ако су исти, онда смо сигурни да је други низ кодирани низ другог. Али ако нису једнаки, проверавамо да ли након сортирања низова. Они су једнаки или не.

Види такође
Зигзаг конверзија

Након сортирања ако су једнаки, постоји могућност да други улаз буде кодирани низ првог. Али ако нису једнаки, сигурни смо да нећемо моћи пронаћи решење тако да је други улаз кодирани низ првог. Сада након свих ових операција, проверавамо да ли је други улаз кодиран или не рекурзивним позивањем функције.

код  

Ц ++ програм за проверу кодираног низа

#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

Јава програм за проверу кодираног низа

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

Анализа сложености  

Сложеност времена

О (2 ^ н) где је н број знакова у првом или другом низу.

Види такође
Преокрените низ помоћу стека

Сложеност простора

О (2 ^ н) јер смо користили 2 ^ н простора за знакове првог и другог низа у програму.