การเรียงสับเปลี่ยน Palindrome


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Facebook ไมโครซอฟท์
กัญชา hashing เชือก

คำชี้แจงปัญหา

ปัญหา“ Palindrome Permutation” ระบุว่าคุณได้รับไฟล์ เชือก. ตรวจสอบว่าสามารถจัดเรียงใหม่เพื่อสร้างสตริง palindromic ได้หรือไม่

ตัวอย่าง

superdupers
yes

คำอธิบาย

สตริงอินพุตที่กำหนดสามารถจัดเรียงใหม่เป็น superdrepus. มันเป็นสตริงแบบ palindromic ดังนั้นคำตอบของเราสำหรับตัวอย่างนี้คือใช่

เข้าใกล้

หากอักขระทั้งหมดเกิดขึ้นเป็นจำนวนครั้งและมากที่สุดหนึ่งอักขระเกิดขึ้นเป็นจำนวนครั้งที่คี่สตริงสามารถแปลงเป็นสตริงแบบ palindromic ได้

ในการนำแนวทางนี้ไปใช้เราจะคงอาร์เรย์นับขนาด 128 ไว้และเริ่มต้นด้วยศูนย์ วนซ้ำผ่านสตริงและเพิ่มจำนวนอักขระแต่ละตัวที่พบในอาร์เรย์ ตอนนี้วนซ้ำผ่านอาร์เรย์และถ้าอักขระอย่างมากที่สุดหนึ่งตัวเกิดขึ้นเป็นจำนวนครั้งที่คี่ให้คืนค่า true else จะคืนค่า false

การเรียงสับเปลี่ยน Palindrome

รหัส

รหัส C ++ สำหรับ Palindrome Permutation

// 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

รหัส Java สำหรับ Palindrome Permutation

// 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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n) เนื่องจากเรากำลังสำรวจอาร์เรย์เพียงครั้งเดียวเพื่อตรวจสอบว่าสตริงที่กำหนดสามารถแปลงเป็นสตริง palindromic ได้หรือไม่ ดังนั้นความซับซ้อนของเวลาจึงกลายเป็น O (n)

ความซับซ้อนของพื้นที่

ความซับซ้อนของช่องว่างสำหรับโปรแกรมเพื่อตรวจสอบว่าสตริงที่กำหนดสามารถแปลงเป็นสตริง palindromic ได้หรือไม่ O (1) เนื่องจากเราใช้อาร์เรย์ขนาด 128 เพื่อเก็บความถี่ของอักขระแต่ละตัว

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้เราจะรักษารายการ จากนั้นเราจะวนซ้ำผ่านสตริงและหากอักขระนั้นมีอยู่แล้วในรายการเราจะลบออกมิฉะนั้นเราจะแทรกอักขระนั้นลงในรายการ หลังจากการทำซ้ำหากจำนวนองค์ประกอบในรายการมากกว่าหนึ่ง ดังนั้นจึงไม่สามารถแปลงเป็นสตริง palindromic

รหัส

โค้ด C ++ ที่ปรับให้เหมาะสมสำหรับ Palindrome Permutation

#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

โค้ด Java ที่ปรับให้เหมาะสมสำหรับ Palindrome Permutation

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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n) เนื่องจากเรากำลังสำรวจอาร์เรย์เพียงครั้งเดียวเพื่อตรวจสอบว่าสตริงที่กำหนดสามารถแปลงเป็นสตริง palindromic ได้หรือไม่ ดังนั้นความซับซ้อนของเวลาจึงกลายเป็น O (n)

ความซับซ้อนของพื้นที่

ความซับซ้อนของพื้นที่สำหรับโปรแกรมเพื่อตรวจสอบว่าสตริงที่กำหนดสามารถแปลงเป็นสตริง palindromic ได้หรือไม่คือ O (1)