Encontrar la subcadena palindrómica más larga es un problema clásico de codificación de entrevistas. Esta publicación resume 3 soluciones diferentes para este problema.
1. Programación dinámica
Sea s la cadena de entrada, i y j son dos índices de la cadena. Defina una «tabla» de matriz de 2 dimensiones y deje que la tabla[i][j] denotar si una subcadena de i a j es palíndromo.
Condición cambiante:
table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j) => table[i][j] == 1
Tiempo O (n ^ 2) Espacio O (n ^ 2)
public String longestPalindrome(String s) { if(s==null || s.length()<=1) return s; int len = s.length(); int maxLen = 1; boolean [][] dp = new boolean[len][len]; String longest = null; for(int l=0; l<s.length(); l++){ for(int i=0; i<len-l; i++){ int j = i+l; if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){ dp[i][j]=true; if(j-i+1>maxLen){ maxLen = j-i+1; longest = s.substring(i, j+1); } } } } return longest; } |
Por ejemplo, si la cadena de entrada es «dabcba», la matriz final sería la siguiente:
1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
En la tabla, podemos ver claramente que la cadena más larga está en la tabla de celdas.[1][5].
2. Un algoritmo simple
Podemos escanear a ambos lados para cada carácter. Tiempo O (n ^ 2), Espacio O (1)
public String longestPalindrome(String s) { if (s.isEmpty()) { return null; } if (s.length() == 1) { return s; } String longest = s.substring(0, 1); for (int i = 0; i < s.length(); i++) { // get longest palindrome with center of i String tmp = helper(s, i, i); if (tmp.length() > longest.length()) { longest = tmp; } // get longest palindrome with center of i, i+1 tmp = helper(s, i, i + 1); if (tmp.length() > longest.length()) { longest = tmp; } } return longest; } // Given a center, either one letter or two letter, // Find longest palindrome public String helper(String s, int begin, int end) { while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) { begin--; end++; } return s.substring(begin + 1, end); } |
3. Algoritmo de Manacher
El algoritmo de Manacher es mucho más complicado de descifrar, aunque traerá el beneficio de la complejidad temporal de O (n). Dado que no es típico, no hay necesidad de perder tiempo en eso.
