南昌网站开发培训学校,简易做海报网站,怎么做软件开发,个人logo在线生成免费题目描述 思路
1.能够反复利用已判断好的回文子串
2.当子串s[i1,j-1]是回文子串时#xff0c;只要s[i]s[j]#xff0c;那么s[i,j]也会是回文子串
3.用好动态规划#xff0c;具体解释在代码注释里
代码
class Solution {public String longestPalindrome(String s) {int…题目描述 思路
1.能够反复利用已判断好的回文子串
2.当子串s[i1,j-1]是回文子串时只要s[i]s[j]那么s[i,j]也会是回文子串
3.用好动态规划具体解释在代码注释里
代码
class Solution {public String longestPalindrome(String s) {int len s.length();//如果是单字符必定是回文直接返回sif(len 2) return s;//dp[][]表示s[i,...,j]是否是回文boolean[][] dp new boolean[len][len];//最长回文子串长度初始化为1int maxLen 1;//最长回文子串左边界初始化为0int begin 0;char[] ch s.toCharArray();//先进行初始化所有单个字符都是回文for(int i 0;i len;i){dp[i][i] true;}//j是右边界for(int j 1;j len;j){//i是左边界for(int i 0;i len;i){//如果左边界大于右边界就退出循环if(i j){break;}if(ch[i] ! ch[j]){dp[i][j] false;}else{//假如子串两边都相等中间只有一个字母直接返回状态trueif(j - i 3){dp[i][j] true;}else{//不然当前状态就由上一个子串决定是由内向外的假如s[2,3]是回文s[1]s[4]//那么s[1,4]也是回文反之如果s[2,3]不是回文那s[1,4]也不会是回文dp[i][j] dp[i1][j-1];}}//当dp[i][j]为true且回文子串长度大于最长长度就更新最长回文子串长度if(dp[i][j] j - i 1 maxLen){maxLen j - i 1;begin i;}}}return s.substring(begin,begin maxLen);}
}
