Scramble ຊ່ອຍແນ່  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ສະ ເໜ່ Samsung
ແບ່ງແລະເອົາຊະນະ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ string ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ  

ບັນຫາເລື່ອງ“ Scramble String” ລະບຸວ່າທ່ານໄດ້ຮັບສອງເຊືອກ. ກວດເບິ່ງວ່າຄັ້ງທີສອງ string ແມ່ນສາຍສະເກັດ ທຳ ອິດຂອງຂໍ້ ທຳ ອິດຫລືບໍ່?

ຄໍາອະທິບາຍ

ໃຫ້ສາຍ s =“ ຍິ່ງໃຫຍ່”

ການເປັນຕົວແທນຂອງ s ເປັນໄມ້ຢືນຕົ້ນຖານສອງໂດຍແບ່ງອອກເປັນສອງສາຍຍ່ອຍທີ່ບໍ່ແມ່ນຫວ່າງ.

Scramble ຊ່ອຍແນ່Pin

ສາຍເຊືອກນີ້ສາມາດຂູດໄດ້ໂດຍການເລືອກເອົາໃບທີ່ບໍ່ແມ່ນໃບໄມ້ແລະແລກປ່ຽນມັນເປັນເດັກນ້ອຍ.

Scramble ຊ່ອຍແນ່Pin

ເພາະສະນັ້ນ "rgeat" ແມ່ນສາຍສັ່ນຂອງສາຍຕົ້ນສະບັບເຊັ່ນ: "ຍິ່ງໃຫຍ່".

ຍົກຕົວຢ່າງ  

s1 = "great"

s2 = "rgeat"
Yes

ຄຳ ອະທິບາຍ: ດັ່ງທີ່ສະແດງຢູ່ຂ້າງເທິງໃນຮູບພາບ, ພວກເຮົາສາມາດເຫັນຜົນໄດ້ຮັບທີ່ຍິ່ງໃຫຍ່“ ດີ”. ແລະຜົນໄດ້ຮັບກໍ່ແມ່ນແມ່ນແລ້ວ.

s1 = "abcde"

s2 = "caebd"
No

 

ສູດການຄິດໄລ່ ສຳ ລັບບັນຫາ Scramble String  

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

ສຳ ລັບການແກ້ໄຂບັນຫານີ້, ກ່ອນອື່ນ ໝົດ, ພວກເຮົາພະຍາຍາມກວດເບິ່ງບາງຢ່າງ. ສິ່ງ ທຳ ອິດທີ່ພວກເຮົາກວດເບິ່ງແມ່ນວ່າທັງສອງເຊືອກແມ່ນເທົ່າກັນຫລືບໍ່. ໂດຍສະ ເໝີ ກັນ, ໃນນີ້ພວກເຮົາ ໝາຍ ຄວາມວ່າຕົວອັກສອນທີ່ຢູ່ໃນຕົວຊີ້ວັດທັງ ໝົດ ຂອງສາຍແມ່ນຄືກັນຫລືບໍ່. ຖ້າພວກມັນຄືກັນ, ຫຼັງຈາກນັ້ນພວກເຮົາແນ່ໃຈວ່າສາຍທີສອງຖືກຂູດຈາກສາຍອື່ນໆ. ແຕ່ຖ້າພວກເຂົາບໍ່ເທົ່າທຽມກັນພວກເຮົາກວດເບິ່ງວ່າຫລັງຈາກຈັດຮຽງແຖວ. ພວກເຂົາເທົ່າທຽມກັນຫລືບໍ່.

ເບິ່ງ
ການປ່ຽນໃຈເຫລື້ອມໃສ Zigzag

ຫຼັງຈາກການຮຽງລໍາດັບຖ້າພວກເຂົາເທົ່າທຽມກັນແລ້ວມັນກໍ່ມີຄວາມເປັນໄປໄດ້ວ່າການປ້ອນຂໍ້ມູນຄັ້ງທີສອງອາດຈະເປັນການລອກລຽນຂອງອັນດັບ ທຳ ອິດ. ແຕ່ຖ້າພວກເຂົາບໍ່ເທົ່າທຽມກັນ, ພວກເຮົາແນ່ໃຈວ່າພວກເຮົາຈະບໍ່ສາມາດຊອກຫາວິທີການແກ້ໄຂໃດໆເຊັ່ນວ່າການປ້ອນຂໍ້ມູນຄັ້ງທີສອງແມ່ນຖືກດຶງເຊືອກຂອງຂໍ້ ທຳ ອິດ. ດຽວນີ້ຫຼັງຈາກການປະຕິບັດງານທັງ ໝົດ ເຫຼົ່ານີ້, ພວກເຮົາກວດເບິ່ງວ່າການປ້ອນຂໍ້ມູນຄັ້ງທີສອງຖືກຂູດຫຼືບໍ່ໂດຍການໂທຫາການເຮັດວຽກຄືນ.

ລະຫັດ  

ໂປຣແກຣມ 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 Program ເພື່ອກວດສອບສາຍເຊືອກທີ່ຂູດໄດ້

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 ແມ່ນ ຈຳ ນວນຕົວອັກສອນໃນແຖວ ທຳ ອິດຫລືສາຍທີສອງ.

ເບິ່ງ
ປີ້ນກັບຄືນສະຕິງໂດຍໃຊ້ Stack

ຄວາມສັບສົນໃນອະວະກາດ

O (2 ^ n) ເພາະວ່າພວກເຮົາໃຊ້ພື້ນທີ່ 2 ^ n ສຳ ລັບຕົວລະຄອນຂອງສາຍ ທຳ ອິດແລະສາຍທີສອງໃນໂປແກມ.

1