סקראַמבלע סטרינג  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן פאנאטיקערס סאַמסונג
צעטיילן און קאַנגקער דינאַמיש פּראָגראַממינג שטריקל בוים

פּראָבלעם סטאַטעמענט  

"סקראַמבלע סטרינג" פּראָבלעם שטאַטן אַז איר האָט צוויי סטרינגס. קוק אויב די רגע שטריקל איז אַ סקראַמבאַלד שטריקל פון ערשטער אָדער נישט?

דערקלערונג

זאל שטריקל s = “גרויס”

פארטרעט פון 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".

פֿאַר סאַלווינג דעם פּראָבלעם, ערשטער פון אַלע, מיר פּרובירן צו קאָנטראָלירן אַ ביסל טינגז. דער ערשטער זאַך וואָס מיר קאָנטראָלירן איז צי ביידע סטרינגס זענען גלייַך אָדער נישט. מיט גלייך, דאָ מיר מיינען אַז אותיות אין אַלע די ינדאַסיז פון די שטריקל זענען די זעלבע אָדער נישט. אויב זיי זענען די זעלבע, מיר זענען זיכער אַז די רגע שטריקל איז סקראַמבאַלד שטריקל פון די אנדערע. אָבער אויב זיי זענען נישט גלייך, מיר קאָנטראָלירן אויב נאָך סאָרטינג די סטרינגס. זיי זענען גלייַך אָדער נישט.

זע אויך
זיגזאַג קאָנווערסיאָן

נאָך סאָרטינג אויב זיי זענען גלייַך, עס איז אַ מעגלעכקייט אַז רגע אַרייַנשרייַב קען זיין אַ סקראַמבאַלד שטריקל פון דער ערשטער. אָבער אויב זיי זענען נישט גלייַך, מיר זענען זיכער אַז מיר קענען נישט געפֿינען קיין לייזונג אַזוי אַז די רגע אַרייַנשרייַב איז סקראַמבאַלד שטריקל פון דער ערשטער. נאָך אַלע די אַפּעריישאַנז, מיר קאָנטראָלירן אויב די רגע אַרייַנשרייַב איז סקראַמבאַלד אָדער ניט רעקורסיוועלי רופן די פֿונקציע.

קאָדעקס  

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (2 ^ ן) וווּ n איז די נומער פון אותיות אין דער ערשטער שטריקל אָדער די רגע שטריקל.

זע אויך
פאַרקערט אַ שטריקל ניצן סטאַק

ספעיס קאַמפּלעקסיטי

אָ (2 ^ ן) ווייַל מיר געוויינט 2 ^ n פּלאַץ פֿאַר אותיות פון דער ערשטער און די רגע שטריקל אין דעם פּראָגראַם.