Palindrome permutation


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Facebook က Microsoft က
hash တားဆီးခြင်း ကြိုး

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

“ Palindrome Permutation” ပြproblemနာကသင့်အားက ကြိုး။ palindromic string ကိုပြန်လည်ဖွဲ့စည်းနိုင်မနိုင်စစ်ဆေးပါ။

နမူနာ

superdupers
yes

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

ပေးထားသော input ကို string ကိုပြန်လည်စီစဉ်နိုင်သည် မင်္ဂလာပါ။ ဒါဟာ palindromic string ကိုဖြစ်ပါတယ်။ ဒီတော့ဒီဥပမာကိုငါတို့အဖြေကဟုတ်တယ်။

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

အကယ်၍ အက္ခရာအားလုံးသည်အကြိမ်အရေအတွက်တောင်မှအများဆုံးအက္ခရာတစ်ခုတွင်အကြိမ်အရေအတွက်ဖြစ်ပေါ်ပါက string ကို palindromic string သို့ပြောင်းလဲနိုင်သည်။

ဤချဉ်းကပ်မှုကိုအကောင်အထည်ဖော်ရန်ကျွန်ုပ်တို့သည် count array အရွယ်အစား 128 ကိုထိန်းသိမ်းပြီးသုညဖြင့်စတင်သည်။ string မှတစ်ဆင့်ကြားဖြတ်ခြင်းနှင့်ခင်းကျင်းပြသခြင်းတွင်တွေ့ရသောဇာတ်ကောင်တစ်ခုစီ၏အရေအတွက်ကိုတိုးမြှင့်ပါ။ ယခု array အားဖြတ်သန်းပါ။ အကယ်၍ စာလုံးတစ်လုံးလျှင်အများဆုံးမရေတွက်နိုင်သောအကြိမ်အရေအတွက်ဖြစ်ပေါ်ပါက true သို့ပြန်သွားပါ။ return false သို့ပြန်သွားပါ။

Palindrome permutation

ကုဒ်

Palindrome permutation များအတွက် C ++ ကုဒ်

// C++ implementation to check if 
// characters of a given string can 
// be rearranged to form a palindrome 
#include<bits/stdc++.h> 
using namespace std; 
#define NO_OF_CHARS 256 

/* function to check whether characters of a string can form 
a palindrome */
bool canFormPalindrome(string str) 
{ 
  // Create a count array and initialize all 
  // values as 0 
  int count[NO_OF_CHARS] = {0}; 

  // For each character in input strings, 
  // increment count in the corresponding 
  // count array 
  for (int i = 0; str[i]; i++) 
    count[str[i]]++; 

  // Count odd occurring characters 
  int odd = 0; 
  for (int i = 0; i < NO_OF_CHARS; i++) 
  { 
    if (count[i] & 1) 
      odd++; 

    if (odd > 1) 
      return false; 
  } 

  // Return true if odd count is 0 or 1, 
  return true; 
} 

/* Driver program*/
int main() 
{ 
canFormPalindrome("superdupers")? cout << "Yes\n": 
                  cout << "No\n"; 
return 0; 
}
Yes

Palindrome permutation အတွက် Java ကုဒ်

// Java implementation to check if 
// characters of a given string can 
// be rearranged to form a palindrome 
import java.io.*; 
import java.util.*; 
import java.math.*; 

class check { 

static int NO_OF_CHARS = 256; 

  /* function to check whether characters 
  of a string can form a palindrome */
  static boolean canFormPalindrome(String str) { 
  
  // Create a count array and initialize all 
  // values as 0 
  int count[] = new int[NO_OF_CHARS]; 
  Arrays.fill(count, 0); 

  // For each character in input strings, 
  // increment count in the corresponding 
  // count array 
  for (int i = 0; i < str.length(); i++) 
  count[(int)(str.charAt(i))]++; 

  // Count odd occurring characters 
  int odd = 0; 
  for (int i = 0; i < NO_OF_CHARS; i++) 
  { 
  if ((count[i] & 1) == 1) 
    odd++; 

  if (odd > 1) 
    return false; 
  } 

  // Return true if odd count is 0 or 1, 
  return true; 
} 

// Driver program 
public static void main(String args[]) 
{ 
  if (canFormPalindrome("superdupers")) 
  System.out.println("Yes"); 
  else
  System.out.println("No"); 

} 
}
Yes

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

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

အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်က array ကိုတစ်ချိန်ကဖြတ်ပြီးပေးထားတဲ့ string ကို palindromic string ကိုပြောင်းလို့ရလားဆိုတာပါ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (n) ဖြစ်လာသည်။

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

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

ထိရောက်သောချဉ်းကပ်မှု

ဒီချဉ်းကပ်မှုမှာတော့ကျနော်တို့စာရင်းကိုထိန်းသိမ်းရန်ပါလိမ့်မယ်။ ထိုအခါကျွန်ုပ်တို့သည် string ကို ဖြတ်၍ ကြားမှာပါလိမ့်မည်။ အကယ်၍ စာလုံးသည်စာရင်းထဲတွင်ရှိနှင့်လျှင်၎င်းကိုဖယ်ရှား။ ၎င်းအက္ခရာကိုစာရင်းထဲသို့ထည့်ပါ။ ကြားမှာပြီးနောက်, စာရင်းထဲတွင်ဒြပ်စင်များ၏နံပါတ်တစျခုထက်သာ။ ကြီးမြတ်လျှင်။ ဒါကို palindromic string အဖြစ်ပြောင်းလို့မရပါဘူး။

ကုဒ်

Palindrome permutation အတွက်အကောင်းဆုံး C ++ ကုဒ်

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

/* 
* function to check whether characters of 
a string can form a palindrome 
*/
bool canFormPalindrome(string str) 
{ 

  // Create a list 
  vector<char> list; 

  // For each character in input strings, 
  // remove character if list contains 
  // else add character to list 
  for (int i = 0; i < str.length(); i++) 
  { 
    auto pos = find(list.begin(), list.end(), str[i]); 
    if (pos != list.end()) 
    { 
      auto posi = find(list.begin(), list.end(),str[i]); 
      list.erase(posi); 
    } 
    else
      list.push_back(str[i]); 
  } 

  // if character length is even list is expected to be empty 
  // or if character length is odd list size is expected to be 1 
  if (str.length() % 2 == 0 && list.empty() // if string length is even 
    || (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd 
    return true; 
  else
    return false; 

} 

// Driver program 
int main() 
{ 
  if (canFormPalindrome("superdupers")) 
    cout << ("Yes") << endl; 
  else
    cout << ("No") << endl; 
}
Yes

Palindrome permutation အတွက်အကောင်းဆုံး Java code

import java.util.ArrayList; 
import java.util.List; 

class check{ 

  /* 
  * function to check whether characters of a string can form a palindrome 
  */
  static boolean canFormPalindrome(String str) { 

    // Create a list 
    List<Character> list = new ArrayList<Character>(); 

    // For each character in input strings, 
    // remove character if list contains 
    // else add character to list 
    for (int i = 0; i < str.length(); i++) { 
      if (list.contains(str.charAt(i))) 
        list.remove((Character) str.charAt(i)); 
      else
        list.add(str.charAt(i)); 
    } 

    // if character length is even list is expected to be empty 
    // or if character length is odd list size is expected to be 1 
    if (str.length() % 2 == 0 && list.isEmpty() // if string length is even 
        || (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd 
      return true; 
    else
      return false; 

  } 

  // Driver program 
  public static void main(String args[]) { 
    if (canFormPalindrome("superdupers")) 
      System.out.println("Yes"); 
    else
      System.out.println("No"); 

  } 
}
Yes

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

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

အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်က array ကိုတစ်ချိန်ကဖြတ်ပြီးပေးထားတဲ့ string ကို palindromic string ကိုပြောင်းလို့ရလားဆိုတာပါ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (n) ဖြစ်လာသည်။

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

ပေးထားသော string ကို palindromic string တစ်ခုသို့ပြောင်းလဲနိုင်ခြင်းရှိမရှိစစ်ဆေးရန်အတွက်အစီအစဉ်အတွက်ရှုပ်ထွေးမှုသည်အို (၁) ဖြစ်သည်။