ခွင့်ပြုချက် permutable နှင့်အတူ palindrome ဖွဲ့စည်းရန်အနည်းဆုံးသွင်း


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ CodeNation နေခြည် Google တကယ်ပါပဲ အလိုလိုသိတတ်သော
Dynamic Programming ကြိုး

ပြpermနာက“ permindations ခွင့်ပြုထားတဲ့ palindrome ကိုဖွဲ့စည်းရန်အနည်းဆုံးထည့်သွင်းမှုများ” ကသင့်ကိုစာလုံးအသေးနဲ့စာလုံးအသေးတစ်ခုစီပေးထားတယ်။ အဆိုပါပြstatementနာကြေညာချက်က Palindrome ဖြစ်လာနိုင်သော string ကိုအနည်းဆုံးထည့်သွင်းရန်ရှာရန်တောင်းဆိုသည်။ ဇာတ်ကောင်တွေရဲ့အနေအထားကို string တစ်ခုနဲ့ပြောင်းနိုင်ပါတယ်။

နမူနာ

ခွင့်ပြုချက် permutable နှင့်အတူ palindrome ဖွဲ့စည်းရန်အနည်းဆုံးသွင်း

malyalam
1

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

ကန ဦး string တွင် 'a' ထည့်နိုင်သည်ဆိုလျှင် palindrome ကိုဖန်တီးနိုင်သည်။

madaam
1

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

မူရင်း string palindrome ပြုလုပ်ရန် 'd' သို့မဟုတ် 'a' ကိုထည့်ပါ။

algorithm

  1. string ကိုအရှည်သတ်မှတ်မည် l နှင့် 0 င်ဖို့ output ကို။
  2. ကြေညာပါ ကိန်း အခင်းအကျင်း.
  3. စာလုံးတစ်ခုစီ၏အရေအတွက်ကို string နှင့်သိမ်းပါ။
  4. ဈ <0 နေချိန်အထိ 26 မှစတင်။ ခင်းကျင်းဖြတ်သန်းပါ။
    1. Check လျှင် countChar [i] % 2 == 1,
      1. မှန်လျှင်, output ကို ++ လုပ်ပါ။
  5. အကယ်၍ output သည် 0 နှင့်ညီလျှင် 0 ကိုပြန်ပို့ပါ။
  6. ကျန်ပြန်လာမှု -၁၁ ။

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

မင်းကို ကြိုးသင်၏တာ ၀ န်ပေးအပ်ထားသည့်အရာမှာ Palindrome ဖြစ်လာစေရန် string တစ်ခုတွင်လုပ်ဆောင်ရန်နိမ့်ဆုံးသွင်းအားစုကိုရှာဖွေရန်ဖြစ်သည်။ ဇာတ်ကောင်တွေရဲ့အနေအထားကို string တစ်ခုနဲ့ပြောင်းနိုင်ပါတယ်။ ကျွန်ုပ်တို့သည် string ၏ဇာတ်ကောင်ဖြစ်ပျက်မှုကိုရေတွက်ပြီး array ထဲသို့သိမ်းဆည်းမည်။ ဘာလို့လဲဆိုတော့နောက်ကွယ်ကအကြံက string တစ်ခု palindrome ဖြစ်တဲ့အခါ string length ကမကိန်းမှာထူးဆန်းတဲ့ character တစ်ခုတည်းပဲရှိလို့ပါ။ ထို့အပြင်အက္ခရာအားလုံးသည်ကြိမ်နှုန်းပင်ရှိသည်။ ဒါကြောင့်မို့လို့အကြိမ်အရေအတွက်မများတဲ့ဇာတ်ကောင်တွေရှာဖို့လိုတယ်။

ကျနော်တို့ input string ကိုအတွက်ဇာတ်ကောင်တိုင်းရေတွက်ခြင်းနှင့်တစ်ခင်းကျင်းဖို့သိုလှောင်သွားနေကြသည်။ ငါတို့ပြောပြီးပြီဆိုရင် palindrome ဆိုတဲ့ string တစ်ခုမှာထူးဆန်းတဲ့အကြိမ်အရေအတွက်အနည်းငယ်သာရှိနိုင်ပါတယ်။ ဒါဆို output က character count ထက်နည်းတယ်။ ဇာတ်ကောင် string တစ်ခုစီတိုင်းကိုသိမ်းဆည်းပြီးတဲ့နောက်။ ပြီးရင် i = 0 to i ကနေ 26 ထက်နည်းသွားတဲ့ array ကိုလုပ်နေတယ်။ ဒါကစုစုပေါင်းအက္ခရာ ၂၆ လုံးရှိတယ်။ ဘာလို့လဲဆိုတော့ပေးထားတဲ့ string တစ်ခုမှာဇာတ်ကောင် ၂၆ ခုရဲ့ဖြစ်နိုင်ခြေရှိလိမ့်မယ်လို့ထင်သင့်တယ်။

Array ကိုဖြတ်သန်းနေစဉ် count တစ်ခုစီကို ၂ နှင့်စားခြင်းကမှန်သည်မှန်လျှင်မှန်သည်၊ ထို့နောက် output ၏ count ကို 2 (output ++) တိုးမည်လားဆိုသည်ကိုကျွန်ုပ်တို့စစ်ဆေးလိမ့်မည်။ array ကို array ပြီးတဲ့နောက် count ကသုညဖြစ်နေရင်၊ စာလုံးမှာဘာမှမရှိဘူး။ ထူးဆန်းတယ်။ string က palindrome ဖြစ်နေပြီ။ ကျွန်တော်တို့ return ပြန်လာလိမ့်မယ် 1 (return-1) output ထုတ်ထားတဲ့ output ထက်နည်းသွားမယ်။ ဇာတ်ကောင်အရေအတွက်နှင့်ဤအရပ်မှကျနော်တို့ output ကိုရတယ်။

ကုဒ်

permindation ခွင့်ပြုထားသော palindrome ကိုဖွဲ့စည်းရန်အနည်းဆုံးသွင်းမှုများကိုရှာရန် C ++ ကုဒ်

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

permindation ခွင့်ပြုထားသော palindrome ကိုဖွဲ့စည်းရန်အနည်းဆုံးထည့်သွင်းရန် Java code ရှိသည်

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (ဎ) ဘယ်မှာ “ n” input ကို string ကိုအတွက်ဇာတ်ကောင်များ၏နံပါတ်ဖြစ်ပါတယ်။

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

အို (၁)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာစဉ်ဆက်မပြတ်အရွယ်အစားရှိတဲ့အပိုခင်းကျင်းကိုဖန်တီးခဲ့တယ်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးစဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။