Dırmaşma String

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Fanatics Samsung
Bölün və fəth edin Dinamik proqramlaşdırma Sim AğacBaxılıb 61

Problem bəyanat

“Dırmaşmaq” problemi sizə iki sim verildiyini bildirir. İkincisinin olub olmadığını yoxlayın sim birincisinin pişmiş bir simli olub, yoxsa yox?

Izahat

Sətir s = “böyük” olsun

Nümayəndəliyi s rekursiv olaraq iki boş olmayan alt sətirə bölməklə ikili ağac kimi.

Dırmaşma StringPin

Bu simli heç bir yarpaq düyünü seçmədən və uşaqlarını dəyişdirərək həll edilə bilər.

Dırmaşma StringPin

Bu səbəbdən “rgeat” orijinal simli, yəni “möhtəşəm” pərçimlənmiş bir sətirdir.

misal

s1 = "great"

s2 = "rgeat"
Yes

İzahat: Yuxarıda şəkillərdə göstərildiyi kimi “böyük” nəticələrin “böyük” ilə qarışdığını görə bilərik. Və nəticədə Bəli.

s1 = "abcde"

s2 = "caebd"
No

 

Scramble String Probleminin alqoritmi

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

bu problemi həll etmək üçün ilk növbədə bir neçə şeyi yoxlamağa çalışırıq. Yoxladığımız ilk şey hər iki simin bərabər olub-olmamasıdır. Eyni şəkildə, burada simli bütün indekslərdəki simvolların eyni və ya eyni olmadığını nəzərdə tuturuq. Əgər onlar eynidirsə, onda ikinci simin o birinin kodlanmış simli olduğuna əminik. Ancaq bərabər deyilsə, ipləri çeşidlədikdən sonra yoxlayırıq. Onlar bərabərdir, ya yox.

Bərabər olduqda çeşidlədikdən sonra ikinci girişin bir-birinin şifrələnmiş sətri olması ehtimalı var. Ancaq bərabər deyilsə, əminik ki, ikinci giriş birincinin şifrələnmiş sətiri olacağı kimi bir həll tapa bilməyəcəyik. İndi bütün bu əməliyyatlardan sonra funksiyanı rekursiv olaraq çağıraraq ikinci girişin pişmiş olub olmadığını yoxlayırıq.

Kodu

Dırmaşma simli yoxlamaq üçün C ++ proqramı

#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

Scramble simli yoxlamaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (2 ^ n) burada n birinci sətirdə və ya ikinci sətirdə simvol sayıdır.

Kosmik Mürəkkəblik

O (2 ^ n) çünki proqramdakı birinci və ikinci simlin simvolları üçün 2 ^ n boşluq istifadə etdik.

Translate »
1