[LeetCode]|[LeetCode] 5. Longest Palindromic Substring [LeetCode]5.LongestPalindromicSubstr

动态规划的解法

class Solution { public String longestPalindrome(String s) { // 设f[i][j]为以s[i]开头s[j]结尾的字符串是否为回文字符串 // f[i][j] = f[i + 1, j - 1] && (s[i] == s[j]) if (s == null || s.length() == 0) { return ""; } if (s.length() == 1) { return s; } int n = s.length(); boolean[][] f = new boolean[n][n]; // 初始条件：一字符回文（j == i） for (int i = 0; i < n; i++) { f[i][i] = true; } // 初始条件：二字符回文（j == i + 1） for (int i = 0, j = 1; j < n; i++, j++) { if (s.charAt(i) == s.charAt(j)) { f[i][j] = true; } } int longestLen = 0; int longestI = 0; int longestJ = 0; for (int i = n - 2; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { // 除去初始条件以外的情况 if (j != i && j != i + 1) { if (j - 1 >= 0) { f[i][j] = f[i + 1][j - 1] && (s.charAt(i) == s.charAt(j)); } } if (f[i][j]) { int len = j - i + 1; if (len > longestLen) { longestLen = len; longestI = i; longestJ = j; } } } } return s.substring(longestI, longestJ + 1); } }

【[LeetCode]|[LeetCode] 5. Longest Palindromic Substring】不得不吐槽一句，这题直接用DP来做有点麻烦！首先两个初始条件你都得想到，除此之外，因为是bottom-up的动态规划，还得考虑计算顺序（画个二维矩阵会更好理解）。