Scramble String


Рівень складності Medium
Часто запитують у Амазонка Фанатики Samsung
Розділяй і володарюй Динамічне програмування рядок Дерево

Постановка проблеми

Проблема “Scramble String” стверджує, що вам дано два рядки. Перевірте, чи другий рядок це шифрований рядок першого чи ні?

Пояснення

Нехай рядок s = "чудовий"

Представництво s як двійкове дерево шляхом рекурсивного розділення його на дві непорожні підрядки.

Scramble String

Цей рядок можна скрембувати, вибравши будь-який нелистовий вузол і помінявши місцями його дочірні.

Scramble String

Тому “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 пробілу для символів першого та другого рядків у програмі.