回文串（三种方法）

 

暴力 o(n3)

中心拓展法o(n2)

动态规划o(n2)

动态规划思路

根据一名分析回文串如果两边字符相同，那么必须中间是回文子串，整体才会回文

既

 且二维遍历，ij确定，子串也就确定，但由于需要先计算出i+1,j-1,所以我们的遍历顺序需要从下往上，既i从大到小，j从小到大，j最小从i开始取
class Solution { public String longestPalindrome(String s) { int len =
s.length(); int ans = 0; int j = 0,i=0; boolean[][] st = new
boolean[1050][1050]; int start = 0,end = 0; for( i=len-1;i>=0;i--) { for(
j=i;j<len;j++) { if(s.charAt(i) == s.charAt(j)){ if((j-i)<=1){ st[i][j] = true;
} else if(st[i+1][j-1]){ st[i][j] = true; } } if(st[i][j]&&(ans<(j-i+1))){ ans
= j-i+1; end = j; start = i; } } } return s.substring(start,end+1); } }

• « 上一篇：SpringBoot配置文件
• » 下一篇：反序输出