מחרוזת לטרוף


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית קנאות סמסונג
הפרד ומשול תכנות דינמי מחרוזת עֵץ

הצהרת בעיה

הבעיה "מחרוזת לטרוף" קובעת שאתה מקבל שני מחרוזות. בדוק אם השני מחרוזת האם מחרוזת מקושקשת של ראשונה או לא?

הסבר

תנו למחרוזת 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

תוכנית 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

ניתוח מורכבות

מורכבות זמן

O (2 ^ n) כאשר n הוא מספר התווים במחרוזת הראשונה או במחרוזת השנייה.

מורכבות בחלל

O (2 ^ n) כי השתמשנו ברווח 2 ^ n עבור תווים מהמחרוזת הראשונה והשנייה בתוכנית.