String ကအခြား String Leetcode Solution ကိုချိုးဖျက်နိုင်မနိုင်စစ်ဆေးပါ


ခက်ခဲအဆင့် အလယ်အလတ်
တည်မြဲခြင်း တပ်မက်သော sorting ကြိုး

ပြProbleနာဖော်ပြချက်

ဒီပြproblemနာမှာငါတို့နှစ်ခုပေးထားတယ် ညှို့ တူညီတဲ့အရွယ်အစား s1 နှင့် s2 ။ string s1 ၏အချို့ permutation string ကို s2 သို့မဟုတ်အပြန်အလှန်အချို့ permutation ကိုချိုးဖျက်နိုင်လျှင်စစ်ဆေးပါ။ တစ်နည်းအားဖြင့် s2 s1 သို့မဟုတ်အပြန်အလှန်ချိုးဖျက်နိုင်ပါတယ်။

i သည် 0 နှင့် n-1 ကြားရှိအားလုံးအတွက် x [i]> = y [i] (အက္ခရာစဉ်အတိုင်း) string y ကို (အရွယ်အစား of နှစ်ခုလုံး) ချိုးနိုင်သည်။

နမူနာ

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

ရှင်းလင်းချက်:

"ayx" s2 = "xc" ၏ permutation ဖြစ်သော string ကို "abc" ကိုချိုးဖျက်နိုင်သည့် s1 = "xya" ၏ permutation ဖြစ်သည်။

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

ရှင်းလင်းချက်:

s1 = "abe" အတွက် permutation အားလုံးမှာ - "abe", "aeb", "bae", "bea", "eab" နှင့် "eba" ။ "," CAD "," cda "," dac "နှင့်" dca "။ သို့သော် s2 မှမည်သည့် permutation မဆို s1 နှင့်အပြန်အလှန်အားဖြင့်အချို့ permutation ကိုချိုးဖျက်နိုင်ပါ။

ချဉ်းကပ်နည်း

ဤပြproblemနာကိုရိုးရိုးရှင်းရှင်းချဉ်းကပ်ခြင်းသည် s1 ၏ permutation တစ်ခုချင်းစီကို s2 တစ်ခုစီ၏ permutation နှင့်အတူစစ်ဆေးရန်ဖြစ်ပြီး၊ အထက်ပါအခြေအနေနှင့်ကိုက်ညီသောစုံတွဲတစ်စုံရှိမရှိကိုရှာဖွေရန်ဖြစ်သည်။ အကယ်၍ string အရွယ်အစားသေးငယ်ပါကဤအရာကိုလုပ်နိုင်သည်။ ဒါပေမယ့်ဒီနေရာမှာ string ရဲ့အရှည်ကအရမ်းကြီးလွန်းလို့ permutation အားလုံးကိုမဖန်တီးနိုင်ဘူး။

ပြstatementနာပြstatementနာကိုဖြေရှင်းခြင်းအားဖြင့်ကျွန်ုပ်တို့သည် string တစ်ခုအားဒုတိယ string ကိုလုံးဝဖုံးအုပ်စေလိုသည်။ အက္ခရာအနေအထားတစ်ခုစီအတွက် string တစ်ခုတွင်ရှိသည့်စာလုံးသည်ဒုတိယ string (အက္ခရာစဉ်အရ) တွင်ရှိသောစာလုံးနှင့်တူညီသည်ထက်ကြီးသင့်သည်ဟူသောသဘောကိုဖုံးကွယ်ထားသည်။ ၎င်းကို string ထဲရှိအက္ခရာများအားလုံးလိုက်နာသင့်သည်။
ယခုလေ့လာမှု၏အဓိကလေ့လာမှုမှာ string အက္ခရာများအားလုံးကိုပထမထက် ပိုမို၍ ကြီးထွားစေလိုလျှင်၊ ကျွန်ုပ်တို့သည် s1 ရှိအသေးစာလုံးငယ်ကို s2 ရှိစာလုံးသေးသေးလေးနှင့်နှိုင်းယှဉ်ရန်ဖြစ်သည်။ အလားတူသာ။ ကြီးမြတ်တ ဦး တည်းနှင့်အတူသာ။ ကြီးမြတ်ဒြပ်စင်။ ဒီ permutation တ ဦး တည်းအခြားချိုးဖောက်သို့မဟုတ်မရှိမရှိစစ်ဆေးအကောင်းဆုံးဖြစ်လိမ့်မည်။ ဥပမာ s1 = "abc" နှင့် s2 = "xya" ။ “ xya” ကိုရွေးချယ်ပြီးနောက်၎င်းသည်အမှတ်တစ်ခုစီတွင်“ abc” ထက်ပိုမိုမြင့်မားလိမ့်မည်။

String ကအခြား String Leetcode Solution ကိုချိုးဖျက်နိုင်မနိုင်စစ်ဆေးပါ

အက္ခရာအားလုံးအတွက် s1 ထက်ပိုပြီး s2 လုပ်နိုင်ရင် true ပြန်လာပါလိမ့်မယ်။ ဒုတိယဖြစ်ရပ်တွင်ကျွန်ုပ်တို့သည် s2 ကို s1 ထက်ပိုမိုကြီးမားအောင်ပြုလုပ်နိုင်ပါကကျွန်ုပ်တို့လည်း true သို့ပြန်သွားသည်။ ဒီလိုမှမဟုတ်ရင်ဘယ်သူမှမချိုးနိုင်ဘူး

Algorithm:

  • အကယ်၍ s1 အရှည်သည် s2 အရှည်နှင့်မတူပါက false သို့ပြန်သွားပါ။
  • ကြိုးနှစ်မျိုးစလုံးကိုအစဉ်လိုက်သို့မဟုတ်အစဉ်လိုက်စီပါ။
  • s1 ၏အက္ခရာများတစ်လျှောက်ကွင်းဆက်တစ်ခု run ပါ။ s1 [i]> = s2 [i] ရှိပါကဇာတ်ကောင်တစ်ခုစီကိုစစ်ဆေးပါ။ ဇာတ်ကောင်အားလုံးဒီအခြေအနေကိုကျေနပ်လျှင်, true ကိုပြန်လာပါ။
  • ယခု s2 ၏အက္ခရာများတစ်လျှောက်ကွင်းဆက်တစ်ခု run ပါ။ s2 [i]> = s1 [i] လျှင်ဇာတ်ကောင်ချင်းစီကိုစစ်ဆေးပါ။ ဇာတ်ကောင်အားလုံးဒီအခြေအနေကိုကျေနပ်လျှင်, true ကိုပြန်လာပါ။
  • အခြားအယူမှားပြန်လာ

အကောင်အထည်ဖော်ရေး

C ++ သည် Program အတွက် String အခြား Stret Leetcode Solution ကိုချိုးဖျက်နိုင်လျှင်စစ်ဆေးပါ

#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

Check for Java Program သည် String Leetcode Solution ကိုအခြား String တစ်ခုဖြင့်ချိုးဖျက်နိုင်လျှင်

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

စစ်ဆေးမှုအတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း String သည်အခြား String Leetcode Solution ကိုချိုးဖျက်နိုင်လျှင်

အချိန်ရှုပ်ထွေး

အို (nlog (n)) ဘယ်မှာ n ပေးထားသော string ကို၏အရှည်သည်။ ပေးထားသော string ကိုနှစ်ကြိမ်မျဉ်းကြောင်းဖြတ်ပြီးစီးခဲ့သည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှု nlogn ဖြစ်လိမ့်မည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁) ကျွန်တော်မှတ်ဥာဏ်ပိုမသုံးခဲ့ပါဘူး အချို့သော sorting algorithms များအတွက် space ရှုပ်ထွေးမှုသည် O (1) ထက်ကြီးနိုင်သည်။