1、题目描述:
2、解题方法:动态规划
动态规划解题步骤:
1、确定状态
-
-
- 最后一步:如果s[i,...,j]是回文子串,那么需要满足两个条件
-
① s[i] == s[j];
② s[i+1,...,j-1]是回文子串;
-
-
- 子问题:我们要验证s[i+1,...,j-1]是不是回文子串
- 用dp[i][j]来表示s[i,...,j]是不是回文子串
-
2、转移方程
dp[i][j] = (s[i] == s[j])&& dp[i+1][j-1]
3、初始条件和边界情况
初始条件:dp[i][i] == true;
边界条件:在s[i] == s[j]的条件下,j-i<=2或者j-i<3,即说明s[i,...,j]的长度为2或者是3时,不用检查是不是回文串。
4、计算顺序
以字符串s:babab为例,一列一列的进行填表,先升序填列,再升序填行。
3、代码:
public String longestPalindrome(String s) { int len = s.length(); if(len < 2){ return s; } int maxLen = 1; int start = 0; char[] res = s.toCharArray(); boolean[][] dp = new boolean[len][len]; for(int i = 0; i < len; i++){ dp[i][i] = true; } for(int j = 1; j < len; j++){ for(int i = 0; i < j; i++){ if(res[i] == res[j]){ if(j - i < 3 || dp[i+1][j-1] == true){ dp[i][j] = true; } if( j-i+1 > maxLen && dp[i][j] == true){ maxLen = j-i+1; start = i; } } } } return s.substring(start,start + maxLen); }
标签:子串,leetcode5,int,len,true,dp,回文 From: https://www.cnblogs.com/LXXin6973/p/16630659.html