Leetcode大佬讲解的很好。这里记录下。两种方法:中心扩散和动态规划。
值得注意的是中心扩散在该题比动态规划好。
public int getLongestPalindrome(String A, int n) { // 中心扩散 if(A == null || n <= 1) return n; int maxLen = 1, left = 0, right = 0, len = 0; for (int i = 0; i < n; i++) { left = i - 1; right = i + 1; while(left >= 0 && A.charAt(left) == A.charAt(i)){ left--; len++; } while(right < n && A.charAt(right) == A.charAt(i)){ right++; len++; } while(left>=0 && right < n && A.charAt(left) == A.charAt(right)){ right++; left--; len += 2; } if(len > maxLen){ maxLen = len; } len = 1; } return maxLen; }
public int getLongestPalindrome(String A, int n) { // 动态规划 if(A==null || n <= 1) return n; int maxLen = 1; boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { dp[i][i] = true; } for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { if(A.charAt(i) == A.charAt(j)){ if(j - i < 3){ dp[i][j] = true; }else{ dp[i][j] = dp[i + 1][j - 1]; } } if(dp[i][j] && j - i + 1 > maxLen){ maxLen = j - i + 1; } } } return maxLen; }