力扣 最长回文子串

双指针，多维动态规划。
标题

回文即顺着读跟倒着读都是一样的，然后又是一个找子串的问题，不难发现又是一道dp了。但是，这里维护的状态用到了双指针，找的分别是子串的首字母跟尾字母，因此也是个多维动态规划。外循环从后往前遍历，内循环从当前点今后遍历，为了方便更新子串的长度，因为要找出最长的即res，找到后即截取对应的字符串。维护的状态有dp[j]，还有res长度。
时间复杂度： O(n^2)，空间复杂度： O(n^2)。

1. class Solution {
2.   public static String longestPalindrome(String s) {
3.         int n = s.length();
4.         // dp[i][j] 表示 i到j是否是回文串
5.         boolean[][] dp = new boolean[n][n];
7.         int res = 0;
8.         String str = "";
9.         for (int i = n - 1; i >= 0; i--) {
10.             //j=i将每个单个字符dp赋为了true
11.             for (int j = i; j < n; j++) {
12.                 if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
13.                     dp[i][j] = true;
14.                     res = Math.max(j - i, res);//更新res
15.                     if (j - i >= res) {
16.                         str = s.substring(i, j + 1);//左闭右开
17.                     }
18.                 }
19.             }
20.         }
21.         return str;
22.     }
23. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。