Leetcode 5 最长回文子串
题目描述:给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
思路:基本的动态规划做法。
1.借助一个二维布尔数组,dd[i][j]为true表示字符串中索引i到j为回文子串,否则反之。
2.以字符串"babac"为例,如下图。
每一个dd[i][j]代表图中一个方格,每个方格中的T和F分别代表当前子串是否为回文字符串,如
dd[0][2]="bab",为回文串,由定义,可以确定图中上三角中方格的值为T。
3.循环判定的原则为str[i] == str[j] && dd[i+1][j-1],若j-i<2 则只满足str[i] == str[j]即可。
4.若当前为回文子串,判断是否比当前的最大回文子串长,若长则更新。
代码如下:
public String longestPalindrome(String s) { int len=s.length(); int max=0; if(s==null||len==0) return s; String rs=""; boolean[][] dd = new boolean[len][len]; //默认值false 仅考虑上三角(i<j) for (int j=0;j<len;j++) for (int i=0;i<=j;i++) { dd[i][j]=(s.charAt(i)==s.charAt(j)&&(j-i<=2||dd[i+1][j-1])); if(dd[i][j]) { if(max<j-i+1) { max = j - i + 1; rs = s.substring(i, j + 1); //substring取子串 包括开始索引,不含结束索引 } } } return rs; }
这只是最简单的动态规划,作为励志刷更多LeetCode的菜鸡,参考了一些其他博主的文章。归纳总结的,希望对大家有用。