力扣-5.最长回文子串

题目链接

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;}
}

小结：双指针可以做居然不超时，但这里还是做了动态规划解法，注意遍历的时候要按照子串长度从小到大遍历，避免跳过。