스크램블 문자열


난이도 중급
자주 묻는 질문 아마존 광신자 삼성
분열과 정복 동적 프로그래밍 나무

문제 정책

“Scramble String”문제는 두 개의 문자열이 주어 졌다는 것을 나타냅니다. 두 번째 확인 스크램블 된 문자열의 첫 번째 문자열입니까?

설명

string s = "great"

대표 s 두 개의 비어 있지 않은 하위 문자열로 재귀 적으로 나눔으로써 이진 트리로.

스크램블 문자열

이 문자열은 리프가 아닌 노드를 선택하고 자식 노드를 교체하여 스크램블 할 수 있습니다.

스크램블 문자열

따라서“rgeat”는 원래 문자열 즉“great”의 스크램블 된 문자열입니다.

s1 = "great"

s2 = "rgeat"
Yes

설명 : 위의 이미지에서 볼 수 있듯이“great”결과가“great”로 뒤섞이는 것을 볼 수 있습니다. 따라서 결과는 예입니다.

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 공백을 사용했기 때문입니다.