java常用算法之最长回文子串(Longest Palindromic Substring)

本文主要是介绍java常用算法之最长回文子串(Longest Palindromic Substring)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

方法一：时间复杂度为O(n^3)

public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {int len = j - i;String curr = s.substring(i, j + 1);if (isPalindrome(curr)) {if (len > maxPalinLength) {longestPalindrome = curr;maxPalinLength = len;}}}}return longestPalindrome;
}public static boolean isPalindrome(String s) {for (int i = 0; i < s.length() - 1; i++) {if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {return false;}}return true;
}

方法二：时间复杂度为 O(n^2)

public static String longestPalindrome2(String s) {if (s == null)return null;if(s.length() <=1)return s;int maxLen = 0;String longestStr = null;int length = s.length();int[][] table = new int[length][length];//every single letter is palindromefor (int i = 0; i < length; i++) {table[i][i] = 1;}printTable(table);//e.g. bcba//two consecutive same letters are palindromefor (int i = 0; i <= length - 2; i++) {if (s.charAt(i) == s.charAt(i + 1)){table[i][i + 1] = 1;longestStr = s.substring(i, i + 2);}	}printTable(table);//condition for calculate whole tablefor (int l = 3; l <= length; l++) {for (int i = 0; i <= length-l; i++) {int j = i + l - 1;if (s.charAt(i) == s.charAt(j)) {table[i][j] = table[i + 1][j - 1];if (table[i][j] == 1 && l > maxLen)longestStr = s.substring(i, j + 1);} else {table[i][j] = 0;}printTable(table);}}return longestStr;
}
public static void printTable(int[][] x){for(int [] y : x){for(int z: y){System.out.print(z + " ");}System.out.println();}System.out.println("------");
}

给一个字符串,我们可以利用方法 printTable() 来输出执行结果. 例如, 字符串 "dabcba"执行上述代码片段后输出结果如下：

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 

从输出结果我们能清晰的看到最长的字符串在table[1][5].

这篇关于java常用算法之最长回文子串(Longest Palindromic Substring)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---