ກວດເບິ່ງວ່າສະຕິງສາມາດ ທຳ ລາຍວິທີແກ້ໄຂ Leetcode ອື່ນໄດ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
endurance ຄວາມໂລບມາກ ຮຽງລໍາດັບ string

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

ໃນບັນຫານີ້ພວກເຮົາໄດ້ຮັບສອງຢ່າງ strings s1 ແລະ s2 ທີ່ມີຂະ ໜາດ ດຽວກັນ. ກວດເບິ່ງວ່າການອະນຸຍາດຂອງສາຍສະຕິງ s1 ສາມາດ ທຳ ລາຍການອະນຸຍາດຂອງສາຍ s2 ຫຼືບາງສະບັບ. ໃນຄໍາສັບຕ່າງໆອື່ນໆ s2 ສາມາດທໍາລາຍ s1 ຫຼືກົງກັນຂ້າມ.

ສາຍ x ສາມາດແຍກສາຍ y (ທັງຂະ ໜາດ n) ຖ້າ x [i]> = y [i] (ຕາມ ລຳ ດັບຕົວອັກສອນ) ສຳ ລັບ i ທັງ ໝົດ ລະຫວ່າງ 0 ແລະ n-1.

ຍົກຕົວຢ່າງ

s1 = "abc", s2 = "xya"
true

ຄໍາອະທິບາຍ:

“ ayx” ແມ່ນອະນຸຍາດຂອງ s2 =” ເຈັດ” ເຊິ່ງສາມາດແຍກເປັນ“ abc” ເຊິ່ງເປັນ permutation ຂອງ s1 =” abc”.

s1 = "abe", s2 = "acd"
false

ຄໍາອະທິບາຍ:

ການອະນຸຍາດທັງ ໝົດ ສຳ ລັບ s1 = "abe" ແມ່ນ: "abe", "aeb", "bae", "bea", "eab" ແລະ "eba" ແລະອະນຸຍາດທັງ ໝົດ ສຳ ລັບ s2 = "acd" ແມ່ນ: "acd", "adc ”,“ cad”,“ cda”,“ dac” ແລະ“ dca”. ເຖິງຢ່າງໃດກໍ່ຕາມ, ມັນບໍ່ມີການອະນຸຍາດໃດໆຈາກ s1 ເຊິ່ງສາມາດ ທຳ ລາຍການອະນຸຍາດ ຈຳ ນວນ ໜຶ່ງ ຈາກ s2 ແລະໃນທາງກັບກັນ.

ວິທີການ

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

ໄປພ້ອມກັບ ຄຳ ຖະແຫຼງທີ່ມີປັນຫາພວກເຮົາຕ້ອງການໃຫ້ສາຍ ໜຶ່ງ ກວມເອົາສາຍທີສອງຢ່າງຄົບຖ້ວນ. ກວມເອົາໃນຄວາມ ໝາຍ ທີ່ວ່າ ສຳ ລັບແຕ່ລະ ຕຳ ແໜ່ງ ຕົວລະຄອນ, ຕົວລະຄອນທີ່ ໜຶ່ງ ສາຍຄວນຈະສູງກວ່າຕົວອັກສອນຢູ່ແຖວທີສອງ (ອີງຕາມ ລຳ ດັບຕົວອັກສອນ). ນີ້ຄວນຈະຖືກຕິດຕາມໂດຍທຸກໆຕົວອັກສອນໃນສາຍ.
ດຽວນີ້ການສັງເກດທີ່ ສຳ ຄັນຢູ່ນີ້ແມ່ນຖ້າພວກເຮົາຕ້ອງການໃຫ້ຕົວອັກສອນທັງ ໝົດ ໃຫຍ່ຂື້ນໃນສາຍ ທຳ ອິດກ່ວາທີສອງແລ້ວພວກເຮົາຕ້ອງປຽບທຽບຕົວອັກສອນນ້ອຍກວ່າໃນ s1 ກັບຕົວອັກສອນນ້ອຍກວ່າໃນ s2. ອົງປະກອບທີ່ຄ້າຍຄືກັນທີ່ມີຫຼາຍກວ່າເກົ່າ. ການອະນຸຍາດນີ້ຈະເປັນການດີທີ່ສຸດເພື່ອກວດກາເບິ່ງວ່າມີຜູ້ ໜຶ່ງ ແຕກແຍກຫລືບໍ່. ຕົວຢ່າງ s1 =” abc” ແລະ s2 =” ເຈັດ”. ຫຼັງຈາກຈັດປະເພດ“ ເຈັດ” ມັນຈະສູງກວ່າ“ abc” ໃນແຕ່ລະຈຸດ.

ກວດເບິ່ງວ່າສະຕິງສາມາດ ທຳ ລາຍວິທີແກ້ໄຂ Leetcode ອື່ນໄດ້

ຖ້າພວກເຮົາສາມາດເຮັດໃຫ້ s1 ໃຫຍ່ກວ່າ s2 ສຳ ລັບໂຕອັກສອນທັງ ໝົດ ແລ້ວພວກເຮົາກໍ່ຈະກັບມາເປັນຄວາມຈິງ. ໃນກໍລະນີທີສອງຖ້າພວກເຮົາສາມາດເຮັດໃຫ້ s2 ໃຫຍ່ກວ່າ s1 ແລ້ວພວກເຮົາກໍ່ຈະກັບຄືນມາເປັນຄວາມຈິງໄດ້. ຖ້າບໍ່ດັ່ງນັ້ນບໍ່ມີໃຜສາມາດທໍາລາຍຄົນອື່ນໄດ້.

ສູດການຄິດໄລ່:

  • ຖ້າຄວາມຍາວຂອງ s1 ບໍ່ເທົ່າກັບຄວາມຍາວຂອງ s2 ແລ້ວສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.
  • ຮຽງທັງສອງເຊືອກຕາມ ລຳ ດັບຫລືລົງ.
  • ດໍາເນີນການ loop ຕາມລັກສະນະຂອງ s1. ກວດເບິ່ງແຕ່ລະຕົວອັກສອນຖ້າ s1 [i]> = s2 [i]. ຖ້າຕົວອັກສອນທັງ ໝົດ ຕອບສະ ໜອງ ເງື່ອນໄຂນີ້ແລ້ວກໍ່ຈະກັບມາເປັນຄວາມຈິງ.
  • ຕອນນີ້ ດຳ ເນີນ loop ຕາມຕົວອັກສອນຂອງ s2. ກວດເບິ່ງແຕ່ລະຕົວອັກສອນຖ້າ s2 [i]> = s1 [i]. ຖ້າຕົວອັກສອນທັງ ໝົດ ຕອບສະ ໜອງ ເງື່ອນໄຂນີ້ແລ້ວກໍ່ຈະກັບມາເປັນຄວາມຈິງ.
  • ຄົນອື່ນສົ່ງຄືນບໍ່ຖືກຕ້ອງ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບກວດເບິ່ງວ່າສະຕິງສາມາດ ທຳ ລາຍວິທີແກ້ Leetcode ອື່ນໄດ້

#include <bits/stdc++.h>
using namespace std;

bool checkIfCanBreak(string s1, string s2)
{
    if(s1.length() != s2.length()) return false;

    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());

    int i=0;
    while(s1[i])
    {
        if(s1[i]<s2[i]) break;
        i++;
    }

    if(i==s1.length()) return true;

    i=0;
    while(s2[i])
    {
        if(s1[i]>s2[i]) break;
        i++;
    }

    if(i==s2.length()) return true;

    return false;
}

int main() 
{
    string s1 = "abc";
    string s2 = "xya";
    if( checkIfCanBreak( s1, s2) )
        cout<< "true" ;
    else
        cout<< "false";
    return 0; 
}
true

Java Program for Check ຖ້າສະຕິງສາມາດ ທຳ ລາຍໂຊລູຊັ່ນ Leetcode ອີກວິທີ ໜຶ່ງ

import java.util.*;
class Rextester{
    
    public static boolean checkIfCanBreak(String s1, String s2) 
    {    
        if(s1.length() != s2.length()) return false;
        
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        
        int i=0;
        while(i<s1.length())
        {
            if(c1[i]<c2[i]) break;
            i++;
        }
        
        if(i==s1.length()) return true;
        
        i=0;
        while(i<s2.length())
        {
            if(c1[i]>c2[i]) break;
            i++;
        }
        
        if(i==s2.length()) return true;
        
        return false;        
    }
    
    public static void main(String args[])
    {
        String s1 = "abc";
        String s2 = "xya";
        System.out.println(checkIfCanBreak( s1, s2) );
    }
}
true

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການກວດສອບຖ້າເຊືອກສາມາດ ທຳ ລາຍວິທີແກ້ໄຂ Leetcode ອື່ນໄດ້

ຄວາມສັບສົນເວລາ

O (nlog (n)): ບ່ອນທີ່ n ແມ່ນຄວາມຍາວຂອງສາຍສະຕິງທີ່ໃຫ້. ພວກເຮົາຈັດຮຽງສາຍເຊືອກທີ່ໄດ້ມອບໃຫ້ແລະຂ້າມມັນສອງເສັ້ນ. ເພາະສະນັ້ນຄວາມສັບສົນເວລາຈຶ່ງຈະບໍ່ຮູ້ຕົວ.

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

O (1): ພວກເຮົາບໍ່ໄດ້ໃຊ້ຄວາມ ຈຳ ພິເສດໃດໆ. ເຖິງແມ່ນວ່າ ສຳ ລັບການຈັດປະເພດອະວະກາດສັບຊ້ອນບາງບ່ອນສາມາດໃຫຍ່ກວ່າ O (1).