題目鏈接

5.最長回文子串

class Solution {public String longestPalindrome(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int maxLen = 0;String str = s.substring(0, 1);for (int i = 0; i < s.length(); i++) {dp[i][i] = true;}for (int len = 2; len <= s.length(); len++) {for (int i = 0; i + len <= s.length(); i++) {int j = i + len - 1;if (len == 2) {dp[i][j] = s.charAt(i) == s.charAt(j);} else {dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];}if (dp[i][j]) {str = s.substring(i, i + len);}}}return str;}
}

小結：雙指針可以做居然不超時，但這里還是做了動態規劃解法，注意遍歷的時候要按照子串長度從小到大遍歷，避免跳過。