የጭረት ገመድ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን አፍቃሪዎች ሳምሰንግ
አካፍል እና ድል ተለዋዋጭ ፕሮግራም ሕብረቁምፊ ዛፍ

የችግሩ መግለጫ

የ “Scramble String” ችግር ሁለት ሕብረቁምፊዎች እንደተሰጠዎት ይናገራል። ሁለተኛው መሆኑን ያረጋግጡ ክር የመጀመሪያው የተሰነጠቀ ገመድ ነው ወይስ አይደለም?

ማስረጃ

ሕብረቁምፊ 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

የጃቫ ፕሮግራም ክርክርን ለማጣራት

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (2 ^ n) በአንደኛው ሕብረቁምፊ ወይም በሁለተኛው ሕብረቁምፊ ውስጥ የቁምፊዎች ቁጥር የት ነው?

የቦታ ውስብስብነት

ኦ (2 ^ n) ምክንያቱም በፕሮግራሙ ውስጥ ለመጀመሪያው እና ለሁለተኛው ገመድ ቁምፊዎች 2 ^ n ቦታን ስለጠቀምን ፡፡