Dada una string de alfabetos en minúsculas. Algunos de los caracteres de la string dada se corrompieron y ahora están representados por *. Podemos reemplazar * con cualquiera de los alfabetos en minúsculas. Tienes que construir lexicográficamente la string de palíndromo más pequeña. Si no es posible construir una impresión de palíndromo «No es posible».
Ejemplos:
Input : str[] = "bc*b" Output : bccb Input : str[] = "bc*a*cb" Output : bcaaacb Input : str[] = "bac*cb" Output : Not Possible
Comience a atravesar la cuerda desde ambos extremos. Digamos que con i=0, j=strlen-1, siga aumentando i y disminuyendo j después de cada iteración hasta que i exceda j. Ahora en cualquier posición intermedia tenemos cinco casos posibles:
- str[i] y str[j] son iguales y tampoco iguales a ‘*’. En este caso, simplemente continúe.
- str[i] y str[j] son iguales y son iguales a ‘*’. Aquí debe completar str[i] = str[j] = ‘a’ para el palíndromo más pequeño posible.
- str[i] es igual a ‘*’ y str[j] es un alfabeto. Aquí complete str[i] = str[j] para hacer de nuestra string un palíndromo.
- str[j] es igual a ‘*’ y str[i] es un alfabeto. Aquí complete str[j] = str[i] para hacer de nuestra string un palíndromo.
- str[i] no es igual a str[j] y también ambos son algún alfabeto. En este caso no es posible la construcción del palíndromo. Por lo tanto, imprima «No es posible» y salga del bucle.
Después de que i exceda j significa que tenemos nuestro palíndromo requerido. De lo contrario, obtuvimos «No es posible» como resultado.
Implementación:
C++
// CPP for constructing smallest palindrome #include <bits/stdc++.h> using namespace std; // function for printing palindrome string constructPalin(string str, int len) { int i = 0, j = len - 1; // iterate till i<j for (; i < j; i++, j--) { // continue if str[i]==str[j] if (str[i] == str[j] && str[i] != '*') continue; // update str[i]=str[j]='a' if both are '*' else if (str[i] == str[j] && str[i] == '*') { str[i] = 'a'; str[j] = 'a'; continue; } // update str[i]=str[j] if only str[i]='*' else if (str[i] == '*') { str[i] = str[j]; continue; } // update str[j]=str[i] if only str[j]='*' else if (str[j] == '*') { str[j] = str[i]; continue; } // else print not possible and return cout << "Not Possible"; return ""; } return str; } // driver program int main() { string str = "bca*xc**b"; int len = str.size(); cout << constructPalin(str, len); return 0; }
Java
// Java for constructing smallest palindrome class GFG { // function for printing palindrome static String constructPalin(char []str, int len) { int i = 0, j = len - 1; // iterate till i<j for (; i < j; i++, j--) { // continue if str[i]==str[j] if (str[i] == str[j] && str[i] != '*') continue; // update str[i]=str[j]='a' if both are '*' else if (str[i] == str[j] && str[i] == '*') { str[i] = 'a'; str[j] = 'a'; continue; } // update str[i]=str[j] if only str[i]='*' else if (str[i] == '*') { str[i] = str[j]; continue; } // update str[j]=str[i] if only str[j]='*' else if (str[j] == '*') { str[j] = str[i]; continue; } // else print not possible and return System.out.println("Not Possible"); return ""; } return String.valueOf(str); } // Driver code public static void main(String[] args) { String str = "bca*xc**b"; int len = str.length(); System.out.println(constructPalin(str.toCharArray(), len)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 for constructing smallest palindrome # function for printing palindrome def constructPalin(string, l): string = list(string) i = -1 j = l # iterate till i<j while i < j: i += 1 j -= 1 # continue if str[i]==str[j] if (string[i] == string[j] and string[i] != '*'): continue # update str[i]=str[j]='a' if both are '*' elif (string[i] == string[j] and string[i] == '*'): string[i] = 'a' string[j] = 'a' continue # update str[i]=str[j] if only str[i]='*' elif string[i] == '*': string[i] = string[j] continue # update str[j]=str[i] if only str[j]='*' elif string[j] == '*': string[j] = string[i] continue # else print not possible and return print("Not Possible") return "" return ''.join(string) # Driver Code if __name__ == "__main__": string = "bca*xc**b" l = len(string) print(constructPalin(string, l)) # This code is contributed by # sanjeev2552
C#
// C# for constructing smallest palindrome using System; class GFG { // function for printing palindrome static String constructPalin(char []str, int len) { int i = 0, j = len - 1; // iterate till i<j for (; i < j; i++, j--) { // continue if str[i]==str[j] if (str[i] == str[j] && str[i] != '*') continue; // update str[i]=str[j]='a' if both are '*' else if (str[i] == str[j] && str[i] == '*') { str[i] = 'a'; str[j] = 'a'; continue; } // update str[i]=str[j] if only str[i]='*' else if (str[i] == '*') { str[i] = str[j]; continue; } // update str[j]=str[i] if only str[j]='*' else if (str[j] == '*') { str[j] = str[i]; continue; } // else print not possible and return Console.WriteLine("Not Possible"); return ""; } return String.Join("",str); } // Driver code public static void Main(String[] args) { String str = "bca*xc**b"; int len = str.Length; Console.WriteLine(constructPalin(str.ToCharArray(), len)); } } // This code contributed by Rajput-Ji
PHP
<?php // PHP for constructing smallest palindrome // function for printing palindrome function constructPalin($str, $len) { $i = 0; $j = $len - 1; // iterate till i<j for (; $i < $j; $i++, $j--) { // continue if str[i]==str[j] if ($str[$i] == $str[$j] && $str[$i] != '*') continue; // update str[i]=str[j]='a' if both are '*' else if ($str[$i] == $str[$j] && $str[$i] == '*') { $str[$i] = 'a'; $str[$j] = 'a'; continue; } // update str[i]=str[j] if only str[i]='*' else if ($str[$i] == '*') { $str[$i] = $str[$j]; continue; } // update str[j]=str[i] if only str[j]='*' else if ($str[$j] == '*') { $str[$j] = $str[$i]; continue; } // else print not possible and return echo "Not Possible"; return ""; } return $str; } // Driver Code $str = "bca*xc**b"; $len = strlen($str); echo constructPalin($str, $len); // This code is contributed by ita_c ?>
Javascript
<script> // javascript for constructing smallest palindrome // function for printing palindrome function constructPalin(str, len) { var i = 0, j = len - 1; // iterate till i<j for (; i < j; i++, j--) { // continue if str[i]==str[j] if (str[i] == str[j] && str[i] != '*') continue; // update str[i]=str[j]='a' if both are '*' else if (str[i] == str[j] && str[i] == '*') { str[i] = 'a'; str[j] = 'a'; continue; } // update str[i]=str[j] if only str[i]='*' else if (str[i] == '*') { str[i] = str[j]; continue; } // update str[j]=str[i] if only str[j]='*' else if (str[j] == '*') { str[j] = str[i]; continue; } // else print not possible and return document.write( "Not Possible"); return ""; } return str.join(""); } // driver program var str = "bca*xc**b".split(""); var len = str.length; document.write( constructPalin(str, len)); </script>
bcacxcacb
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi . 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.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA