力扣hot100 长回文子串 中心扩散法 动态规划 一题多解 满注释版
Problem: 5. 最长回文子串
文章目录
- 思路
- 💖 中心扩散法
- 💖 DP
思路
👨🏫 参考
💖 中心扩散法
class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}int strLen = s.length();int maxStart = 0; //最长回文串的起点int maxEnd = 0; //最长回文串的终点int maxLen = 1; //最长回文串的长度boolean[][] dp = new boolean[strLen][strLen];for (int r = 1; r < strLen; r++) {for (int l = 0; l < r; l++) {if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {dp[l][r] = true;if (r - l + 1 > maxLen) {maxLen = r - l + 1;maxStart = l;maxEnd = r;}}}}return s.substring(maxStart, maxEnd + 1);}}
💖 DP
class Solution {public String longestPalindrome(String s){if (s == null || s.length() == 0)return "";int n = s.length();char[] ss = s.toCharArray();int maxLen = 1;int begin = 0;// 默认为 falseboolean[][] f = new boolean[n][n];// f[i][j] 表示 s的闭区间[i,j] 是否回文for (int i = 0; i < n; i++)f[i][i] = true;// 长度为 1 的所有子串都是回文的for (int k = 2; k <= n; k++)//先枚举长度{for (int i = 0; i < n; i++)//枚举起点{int j = k + i - 1;//枚举终点if (j >= n)//越界break;//当前的起点和终点相同；2，3个的情况 || 中间的是回文串if (ss[i] == ss[j] && (j - i < 3 || f[i + 1][j - 1]))f[i][j] = true;if (f[i][j] && j - i + 1 > maxLen){maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}
}