Strings Equal လုပ်ရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်များ Leetcode Solution


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

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

မင်းကိုနှစ်ခုပေးထားတယ် ညှို့ s1 နှင့် s2 သည်အက္ခရာများ“ x” နှင့်“ y” တို့ပါဝင်သည်။ မတူညီတဲ့ကြိုးတွေနဲ့သက်ဆိုင်တဲ့စာလုံးနှစ်လုံးကိုလဲလဲလှယ်နိုင်တယ်။
မင်းရဲ့တာဝန်က string နှစ်ခုလုံးကိုညီမျှအောင်လုပ်ဖို့ဖြစ်တယ်။ Strings နှစ်ခုစလုံးကိုညီမျှစေရန်မဖြစ်နိုင်ပါကနှစ်ခုလုံးကို string ဖြစ်စေရန် -1 ဖြစ်ရန်လိုအပ်သော swaps အနည်းဆုံးနံပါတ်ကိုပြန်ပေးပါ။

နမူနာ

#1

s1 = "xx", s2 = "yy"
1

#2

s1 = "xy", s2 = "yx"
2

ချဉ်းကပ်မှု (လောဘ)

string နှစ်ခုလုံးကို ith Index မှာကြည့်လိုက်ရင်ဖြစ်နိုင်သမျှအတွဲ ၄ ခုပဲ {s4 [i], s1 [i]}: {"x", "x"}, {"y" ကိုတွေ့နိုင်ပါတယ်။ , "y"}, {"x", "y"}, {"y", "x"} ။
ပထမအတွဲနှစ်မျိုးအတွက် s1 [i] သည် s2 [i] (ကျွန်ုပ်တို့လိုချင်သောအရာ) နှင့်ညီသည်။ ထိုကဲ့သို့သောကိစ္စရပ်များအတွက်လိုအပ်သောလဲလှယ်မှုနှုန်းသည်သုညဖြစ်သည်။

ကျန်တဲ့အတွဲအားလုံးအတွက် s1 [i] ဟာ s2 [i] နဲ့မတူတဲ့အတွက် swap operations ကိုသုံးဖို့လိုပါတယ်။

ဒါကိုနည်းလမ်းနှစ်နည်းနဲ့သုံးနိုင်တယ်။

(i) i နှင့် j နှစ်ခုစလုံးတွင်တတိယ (သို့မဟုတ် 3th) type pair ရှိလျှင် (i သည် j နှင့်မတူပါ)၊ s4 [i] ကို s1 [j] ဖြင့်လဲလှယ်ပါက s2 [i] သည် s1 နှင့်ညီသွားမည်။ [i] (ဆိုလိုသည်မှာ s [i] = s2 [i])
နှင့် s1 [j] s2 [j] (ဆိုလိုသည်မှာ s1 [j] = s2 [j]) နှင့်ညီမျှလိမ့်မည်။ ဆိုလိုသည်မှာတစ်လှည့်စီတွင် s1 [i] = s2 [i] နှင့် s1 [j] = s2 [လုပ်နိုင်သည်] ကိုဆိုလိုသည်။ ည]

Strings Equal လုပ်ရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်များ Leetcode Solution

 

(၂) ကျွန်ုပ်တို့သည်အညွှန်းကိန်း (i) တွင်တတိယအမျိုးအစား (၃) မျိုးနှင့်အချို့သောညွှန်းကိန်းည (သို့မဟုတ်အပြန်အလှန်) တွင် ၄ မျိုးရှိလျှင် - {"x", "y"}, {"y", "x"} ။ ဒါကြောင့် s3 [i] = s4 [i] နဲ့
s1 [j] = s2 [j] ကိုနှစ်ခါလဲရန်လိုသည်၊ ပထမ ဦး ဆုံး s1 [i] ကို s2 [i] ဖြင့်လဲရန်လိုသည်။ ယခုအတွဲများသည် {{y », "x"}, {"y, "x"} ။ ယခုကျွန်ုပ်တို့သည် s1 [j] နှင့်အတူ s2 [i] ကိုလဲရန်လိုအပ်ပြီးကျွန်ုပ်တို့ရရှိလိမ့်မည်
s1 [i] = s2 [i] နှင့် s1 [ည] = s2 [ည] ။

 

Strings Equal လုပ်ရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်များ Leetcode Solution

 

ကျွန်ုပ်တို့တွေ့မြင်နိုင်သည့် (i) type လုပ်ဆောင်မှုသည်အညွှန်းနှစ်ခုကိုဖြေရှင်းရန် ၁ ချက်သာကြာသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် (i) လုပ်ဆောင်မှုများကိုတတ်နိုင်သမျှပြုလုပ်ရန်ကြိုးစားလိမ့်မည်။ ငါတို့အလွယ်တကူရေတွက်နိုင်တယ်
အားလုံးအတွက်အမျိုးအစား။ ငါတို့ {{x "," y "} အားလုံးအတွက် = n1, {" y "," x "} အတွဲ = n2 အရေအတွက်ကိုရမယ်ဆိုပါစို့။
ကျွန်တော်တစ်မျိုးတည်းလဲလှယ်ခြင်းဖြင့်အမျိုးအစား ၃ စုံ ၂ ခုကိုအခြေချနိုင်သည်။ ထို့ကြောင့် n2 အတွဲများကိုစုစည်းရန်လိုအပ်သော swap သည် n3 / 1 ဖြစ်လိမ့်မည်၊ အကယ်၍ n1 မကိန်းတစ်ခုသည် pair တစုံသည်မတည်မငြိမ်ဖြစ်နေလိမ့်မည်။

n2 များအတွက်အလားတူပင်။ အကယ်၍ n1 နှင့် n2 နှစ်ခုစလုံးသည်ထူးဆန်းလျှင်ကျွန်ုပ်တို့သည် unettled တစ်ခုစီ၏ pair တစုံကိုရရှိလိမ့်မည်။ ထို့ကြောင့် (ii) type ကို အသုံးပြု၍ ၎င်းကိုဖြေရှင်းရန် swaps 2 ခုလိုအပ်သည်။
မဟုတ်ပါက n1 နှင့် n2 ၏ကွာခြားမှုသည်အတူတူပင်မဟုတ်လျှင် (ဆိုလိုသည်မှာ n1 သည်မကိန်း၊ n2 သည်ညီမျှလျှင်) သို့ဖြစ်လျှင်ကျွန်ုပ်တို့သည်အတည်မပြုရသေးသော pair တစုံကိုရရှိလိမ့်မည်။
ထိုသို့ဖြစ်လျှင် string များကိုတန်းတူညီမျှဖြစ်စေရန်မဖြစ်နိုင်ပါ။

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

Strings Equal Leetcode Solution လုပ်ရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်အတွက် C ++ အစီအစဉ်

#include<bits/stdc++.h>
using namespace std;
int minimumSwap(string s1, string s2) 
{
    int xy_count=0,//count of {x,y} pairs
    yx_count=0,//count of {y,x} pairs
    n=s1.length();
    for(int i=0;i<n;i++)
    {
        if(s1[i]!=s2[i])
        {
            if(s1[i]=='x') xy_count++;
            else yx_count++;
        }
    }
    if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+(xy_count%2==1);//if parity of count of xy pair and yx pair is same 
    else return -1;
}

int main()
{
    string s1="xxxyy",s2="yyxxx";
    cout<<minimumSwap(s1,s2);
    return 0;
}
2

Strings Equal Leetcode Solution လုပ်ရန်အနည်းဆုံးလဲလှယ်ရန်အတွက် Java Program

class Rextester{
    
      public static int minimumSwap(String s1, String s2) 
      {
         
        int xy_count=0,//count of {x,y} pairs
        yx_count=0,//count of {y,x} pairs
        n=s1.length();
        for(int i=0;i<n;i++)
        {
            if(s1.charAt(i)!=s2.charAt(i))
            {
                if(s1.charAt(i)=='x') xy_count++;
                else yx_count++;
            }
        }

        //if parity of count of xy pair and yx pair is same 
        if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+((xy_count%2==1)?1:0);
        else return -1;
    }
    
    public static void main(String args[])
    {
       	String s1="xxxyy",s2="yyxxx";
        System.out.println(minimumSwap(s1,s2) );
    }
}
2

Strings Equal Leetcode Solution လုပ်ရန်အနည်းဆုံးလဲလှယ်ရေးအစီအစဉ်အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း

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

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

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

အို (၁) ကျွန်တော်တို့ဟာအပိုအာကာသကိုမသုံးပါ။