Scramble სიმებიანი


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ფანატიკა Samsung
Დაყავი და იბატონე დინამიური პროგრამირება სიმებიანი ხე

პრობლემის განცხადება

”Scramble String” პრობლემა აცხადებს, რომ გეძლევათ ორი სტრიქონი. შეამოწმეთ თუ არა მეორე სიმებიანი შერეული სტრიქონი პირველია თუ არა?

განმარტება

მოდით string s = "great"

წარმომადგენლობა s როგორც ორობითი ხე, რეკურსიულად დაყოფა იგი ორ არაცარიელ ქვე-სტრიქონად.

Scramble სიმებიანი

ამ სტრიქონის დაჭრა შესაძლებელია ნებისმიერი ფოთლოვანი კვანძის არჩევით და მისი ბავშვების შეცვლით.

Scramble სიმებიანი

ამიტომ "rgeat" არის ორიგინალი სტრიქონის ნაკადი, ანუ "დიდი".

მაგალითი

s1 = "great"

s2 = "rgeat"
Yes

განმარტება: როგორც ზემოთ ნაჩვენებია სურათებში, ჩვენ ვხედავთ "დიდი" -ს "დიდი" შედეგებს. ამრიგად, შედეგი არის დიახ.

s1 = "abcde"

s2 = "caebd"
No

 

Scramble სიმების პრობლემის ალგორითმი

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

ჯავა პროგრამა ნაკაწრების სტრიქონის სანახავად

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 სივრცე პირველი და მეორე სტრიქონის სიმბოლოებისთვის.