Hemos dado una string de anagrama y tenemos que comprobar si se puede hacer palíndromo o no.
Ejemplos:
Input : geeksforgeeks Output : No There is no palindrome anagram of given string Input : geeksgeeks Output : Yes There are palindrome anagrams of given string. For example kgeesseegk
Este problema es básicamente el mismo que Verificar si los caracteres de una string determinada se pueden reorganizar para formar un palíndromo . Podemos hacerlo en tiempo O(n) usando una array de conteo. Los siguientes son pasos detallados.
1) Cree una array de conteo de tamaño alfabético que normalmente es 256. Inicialice todos los valores de la array de conteo como 0.
2) Recorra la string dada e incremente el conteo de cada carácter.
3) Atraviese la array de conteo y si la array de conteo tiene más de un valor impar, devuelva falso. De lo contrario, devuelve verdadero.
C++
#include <iostream> 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 to test to print printDups*/ int main() { canFormPalindrome("geeksforgeeks") ? cout << "Yes\n" : cout << "No\n"; canFormPalindrome("geeksogeeks") ? cout << "Yes\n" : cout << "No\n"; return 0; }
Java
// Java program to Check if any anagram // of a string is palindrome or not public class GFG { static final 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]; // For each character in input strings, // increment count in the corresponding // count array for (int i = 0; i < str.length(); i++) count[str.charAt(i)]++; // Count odd occurring characters int odd = 0; for (int i = 0; i < NO_OF_CHARS; i++) { if ((count[i] & 1) != 0) odd++; if (odd > 1) return false; } // Return true if odd count is 0 or 1, return true; } /* Driver program to test to print printDups*/ public static void main(String args[]) { System.out.println(canFormPalindrome("geeksforgeeks") ? "Yes" : "No"); System.out.println(canFormPalindrome("geeksogeeks") ? "Yes" : "No"); } } // This code is contributed by Sumit Ghosh
Python
NO_OF_CHARS = 256 """ function to check whether characters of a string can form a palindrome """ def canFormPalindrome(string): # Create a count array and initialize all # values as 0 count = [0 for i in range(NO_OF_CHARS)] # For each character in input strings, # increment count in the corresponding # count array for i in string: count[ord(i)] += 1 # Count odd occurring characters odd = 0 for i in range(NO_OF_CHARS): if (count[i] & 1): odd += 1 if (odd > 1): return False # Return true if odd count is 0 or 1, return True # Driver program to test to print printDups if(canFormPalindrome("geeksforgeeks")): print "Yes" else: print "No" if(canFormPalindrome("geeksogeeks")): print "Yes" else: print "NO" # This code is contributed by Sachin Bisht
C#
// C# program to Check if any anagram // of a string is palindrome or not using System; public class GFG { static int NO_OF_CHARS = 256; /* function to check whether characters of a string can form a palindrome */ static bool canFormPalindrome(string str) { // Create a count array and // initialize all values as 0 int[] count = new int[NO_OF_CHARS]; // For each character in input // strings, increment count in // the corresponding count array for (int i = 0; i < str.Length; i++) count[str[i]]++; // Count odd occurring characters int odd = 0; for (int i = 0; i < NO_OF_CHARS; i++) { if ((count[i] & 1) != 0) odd++; if (odd > 1) return false; } // Return true if odd count // is 0 or 1, return true; } // Driver program public static void Main() { Console.WriteLine( canFormPalindrome("geeksforgeeks") ? "Yes" : "No"); Console.WriteLine( canFormPalindrome("geeksogeeks") ? "Yes" : "No"); } } // This code is contributed by vt_m.
Javascript
<script> // Javascript program to Check if any anagram // of a string is palindrome or not let NO_OF_CHARS = 256; /* function to check whether characters of a string can form a palindrome */ function canFormPalindrome(str) { // Create a count array and // initialize all values as 0 let count = new Array(NO_OF_CHARS); count.fill(0); // For each character in input // strings, increment count in // the corresponding count array for (let i = 0; i < str.length; i++) count[str[i].charCodeAt()]++; // Count odd occurring characters let odd = 0; for (let i = 0; i < NO_OF_CHARS; i++) { if ((count[i] & 1) != 0) odd++; if (odd > 1) return false; } // Return true if odd count // is 0 or 1, return true; } document.write(canFormPalindrome("geeksforgeeks")? "Yes" + "</br>" : "No" + "</br>"); document.write(canFormPalindrome("geeksogeeks")? "Yes" : "No"); // This code is contributed by divyeshrabadiya07. </script>
Producción:
No Yes
Complejidad de tiempo : O(n)
Espacio auxiliar : O(n).
Este artículo es una contribución de Aarti_Rathi y Rishabh Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 2:
Usando funciones integradas y lógica/algo de la siguiente manera:
- Cree una array de conteo de tamaño alfabético que normalmente es 256. Inicialice todos los valores de la array de conteo como 0.
- Recorre la string dada e incrementa el conteo de cada carácter.
- Recorra la array de conteo y si la array de conteo tiene más de un valor impar, devuelva falso. De lo contrario, devuelve verdadero.
Podemos usar el módulo de colecciones para reducir el número de líneas de código sin contarlo manualmente usando el diccionario.
Python3
from collections import Counter def isPossible(S): a=Counter(S) #create the dictionary of characters which has the count of characters in String a=dict(a) #print(a) c=0 #Iterate through the values for v in a.values(): # To chech odd or not if v%2==1: c+=1 if c>1: return False return True # contributed by Raghavendra SN q=isPossible('geeksogeeks') print(q) z=isPossible('geeksforgeeks') print(z)
True False
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA