スクランブル文字列


難易度 ミディアム
よく聞かれる Amazon (アマゾン) 狂信者 サムスン
分割統治 動的計画法 文字列

問題文

「スクランブル文字列」の問題は、XNUMXつの文字列が与えられていることを示しています。 XNUMX番目かどうかを確認します 文字列 最初のもののスクランブルされた文字列ですか?

説明

文字列s =“ great”とします

の表現 s 空でないXNUMXつのサブ文字列に再帰的に分割することにより、バイナリツリーとして。

スクランブル文字列

この文字列は、リーフ以外のノードを選択し、その子を交換することでスクランブルできます。

スクランブル文字列

したがって、「rgeat」は元の文字列のスクランブルされた文字列、つまり「great」です。

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".

この問題を解決するために、まず、いくつかのことを確認しようとします。 最初にチェックするのは、両方の文字列が等しいかどうかです。 等しいとは、ここでは、文字列のすべてのインデックスの文字が同じであるかどうかを意味します。 それらが同じである場合、XNUMX番目の文字列は他の文字列のスクランブルされた文字列であると確信しています。 しかし、それらが等しくない場合は、文字列をソートした後にチェックします。 それらは等しいかどうか。

それらが等しい場合にソートした後、XNUMX番目の入力が最初の入力のスクランブルされた文字列である可能性があります。 しかし、それらが等しくない場合、XNUMX番目の入力が最初の入力のスクランブルされた文字列であるような解決策を見つけることができないと確信しています。 これらすべての操作の後、関数を再帰的に呼び出すことにより、XNUMX番目の入力がスクランブルされているかどうかを確認します。

コード

スクランブル文字列をチェックする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は最初の文字列またはXNUMX番目の文字列の文字数です。

スペースの複雑さ

O(2 ^ n) プログラムの最初と2番目の文字列の文字にXNUMX ^ nスペースを使用したためです。