جدوجہد سٹرنگ


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون فانٹکس سیمسنگ
تقسیم اور فتح متحرک پروگرامنگ سلک درخت

مسئلہ یہ بیان

"سکریبل سٹرنگ" مسئلہ بیان کرتا ہے کہ آپ کو دو تاریں دی گئی ہیں۔ چیک کریں اگر دوسرا ہے سٹرنگ سب سے پہلے کی ایک scrambled تار ہے یا نہیں؟

وضاحت

سٹرنگ 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".

اس مسئلے کو حل کرنے کے لئے ، سب سے پہلے ، ہم کچھ چیزوں کو جانچنے کی کوشش کرتے ہیں۔ پہلی چیز جس کی ہم جانچ پڑتال کرتے ہیں وہ یہ ہے کہ دونوں کے تار برابر ہیں یا نہیں۔ مساوی ، یہاں ہمارا مطلب ہے کہ سٹرنگ کے تمام انڈیکس میں حرف ایک جیسے ہیں یا نہیں۔ اگر وہ یکساں ہیں تو ، پھر ہمیں یقین ہے کہ دوسری تار دوسرے کے ٹکڑے ٹکڑے کر رہی ہے۔ لیکن اگر وہ برابر نہیں ہیں تو ہم چیک کرتے ہیں کہ ڈوروں کو ترتیب دینے کے بعد۔ وہ برابر ہیں یا نہیں۔

چھانٹنے کے بعد اگر وہ برابر ہیں تو پھر امکان موجود ہے کہ دوسرا ان پٹ پہلے کی کھجلی کھڑا ہوسکتا ہے۔ لیکن اگر وہ برابر نہیں ہیں تو ہمیں یقین ہے کہ ہم کوئی ایسا حل تلاش نہیں کرسکیں گے کہ دوسرا ان پٹ پہلے والے حصے میں اسکرنگڈ سٹرنگ ہو۔ اب ان ساری کاروائیوں کے بعد ، ہم جانچتے ہیں کہ آیا دوسرا ان پٹ اسکرمبل ہے یا نہیں ، اس کے بارے میں بار بار تقریب کو کال کرکے۔

ضابطے

سی ++ پروگرام اسکریبل سٹرنگ کو چیک کرنے کے لئے

#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 جگہ استعمال کی۔