رشته تقلا


سطح دشواری متوسط
اغلب در آمازون متعصبان سامسونگ
تفرقه بینداز و حکومت کن برنامه نویسی پویا رشته درخت

بیان مسأله

مسئله "Scramble String" بیان می کند که دو رشته به شما داده می شود. مورد دوم را بررسی کنید رشته آیا یک رشته درهم است از اولین یا نه؟

توضیح

بگذارید رشته s = "عالی" باشد

نمایندگی 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

برنامه جاوا برای بررسی رشته تقلا

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 فضای برای نویسه های رشته اول و دوم در برنامه استفاده کردیم.