Կռվել լարային


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Ֆանատիկա Samsung
Բաժանել եւ նվաճել Դինամիկ ծրագրավորում String ծառ

Խնդիրի հայտարարություն

«Scramble String» խնդիրը նշում է, որ ձեզ տրվում է երկու տող: Ստուգեք երկրորդը լարային առաջինի խառնված լարն է, թե ոչ:

բացատրություն

Եկեք տողը s = "great"

Ներկայացուցչություն s որպես երկուական ծառ ՝ հետադարձաբար բաժանելով այն երկու ոչ դատարկ ենթալարերի:

Կռվել լարային

Այս տողը կարող է խառնվել `ընտրելով ցանկացած ոչ տերևային հանգույց և փոխելով իր երեխաներին:

Կռվել լարային

Հետևաբար «rgeat» - ը սկզբնական տողի խառնաշփոթ լար է, այսինքն `« մեծ »:

Օրինակ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (2 ^ n) որտեղ n առաջին նիշի կամ երկրորդ տողի նիշերի քանակն է:

Տիեզերական բարդություն

O (2 ^ n) քանի որ ծրագրի մեջ օգտագործեցինք 2 ^ n տարածք առաջին և երկրորդ լարերի նիշերի համար: