ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫೇಸ್ಬುಕ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಹ್ಯಾಶ್ ಹ್ಯಾಶಿಂಗ್ ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆ” ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಸ್ಟ್ರಿಂಗ್. ಪಾಲಿಂಡ್ರೊಮಿಕ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ರೂಪಿಸಲು ಅದನ್ನು ಮರುಹೊಂದಿಸಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.

ಉದಾಹರಣೆ

superdupers
yes

ವಿವರಣೆ

ಕೊಟ್ಟಿರುವ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಮರುಹೊಂದಿಸಬಹುದು ಸೂಪರ್ ಡ್ರೆಪಸ್. ಇದು ಪಾಲಿಂಡ್ರೋಮಿಕ್ ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆ. ಆದ್ದರಿಂದ ಈ ಉದಾಹರಣೆಗೆ ನಮ್ಮ ಉತ್ತರ ಹೌದು.

ಅಪ್ರೋಚ್

ಎಲ್ಲಾ ಅಕ್ಷರಗಳು ಸಹ ಹಲವಾರು ಬಾರಿ ಸಂಭವಿಸಿದಲ್ಲಿ ಮತ್ತು ಒಂದು ಅಕ್ಷರವು ಬೆಸ ಸಂಖ್ಯೆಯ ಬಾರಿ ಸಂಭವಿಸಿದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಪಾಲಿಂಡ್ರೊಮಿಕ್ ಸ್ಟ್ರಿಂಗ್ ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದು.

ಈ ವಿಧಾನವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ನಾವು 128 ಗಾತ್ರದ ಎಣಿಕೆ ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ ಮತ್ತು ಶೂನ್ಯದೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. ಸ್ಟ್ರಿಂಗ್ ಮೂಲಕ ಪುನರಾವರ್ತಿಸಿ ಮತ್ತು ರಚನೆಯಲ್ಲಿ ಎದುರಾದ ಪ್ರತಿಯೊಂದು ಪಾತ್ರದ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸಿ. ಈಗ ರಚನೆಯ ಮೂಲಕ ಪುನರಾವರ್ತಿಸಿ ಮತ್ತು ಒಂದು ಅಕ್ಷರವು ಬೆಸ ಸಂಖ್ಯೆಯ ಬಾರಿ ಸಂಭವಿಸಿದಲ್ಲಿ ನಿಜಕ್ಕೆ ಹಿಂತಿರುಗಿ ಇಲ್ಲದಿದ್ದರೆ ತಪ್ಪಾಗಿ ಹಿಂತಿರುಗಿ.

ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆ

ಕೋಡ್

ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆಗಾಗಿ ಸಿ ++ ಕೋಡ್

// 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 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) ಆಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಪಾಲಿಂಡ್ರೊಮಿಕ್ ಸ್ಟ್ರಿಂಗ್ ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಪ್ರೋಗ್ರಾಂನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ ಒ (1) ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ಪಾತ್ರದ ಆವರ್ತನವನ್ನು ಸಂಗ್ರಹಿಸಲು 128 ಗಾತ್ರದ ಶ್ರೇಣಿಯನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಸಮರ್ಥ ವಿಧಾನ

ಈ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಪಟ್ಟಿಯನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ಸ್ಟ್ರಿಂಗ್ ಮೂಲಕ ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ ಮತ್ತು ಅಕ್ಷರವು ಈಗಾಗಲೇ ಪಟ್ಟಿಯಲ್ಲಿದ್ದರೆ ನಾವು ಅದನ್ನು ತೆಗೆದುಹಾಕುತ್ತೇವೆ ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಆ ಪಾತ್ರವನ್ನು ಪಟ್ಟಿಗೆ ಸೇರಿಸುತ್ತೇವೆ. ಪುನರಾವರ್ತನೆಯ ನಂತರ, ಪಟ್ಟಿಯಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ. ಆದ್ದರಿಂದ, ಇದನ್ನು ಪಾಲಿಂಡ್ರೋಮಿಕ್ ಸ್ಟ್ರಿಂಗ್ ಆಗಿ ಪರಿವರ್ತಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ.

ಕೋಡ್

ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆಗಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಸಿ ++ ಕೋಡ್

#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

ಪಾಲಿಂಡ್ರೋಮ್ ಕ್ರಮಪಲ್ಲಟನೆಗಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಜಾವಾ ಕೋಡ್

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) ಆಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಪಾಲಿಂಡ್ರೊಮಿಕ್ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಪರಿವರ್ತಿಸಬಹುದೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಪ್ರೋಗ್ರಾಂನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆ O (1) ಆಗಿದೆ.