【LeetCode】最长回文子串 (字符串,动态规划)
【LeetCode】最长回文子串 (字符串,动态规划)
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例2:
输入: “cbbd”
输出: “bb”
1.暴力解法
通过三个循环嵌套,前两个循环控制截取字符串的长度与起始点向右的移动,第三个循环是进行字符的回文匹配。所以暴力解法的时间复杂度是O(n的3次方)。
public String longestPalindrome(String s) {
int len = s.length();
if(len<2)
return s;
char c[] = s.toCharArray();
int maxLen = 0;
int start = 0;
for(int i=0;i<len;i++) {
for(int j=i+1;j<len;j++) {
if(j-i>maxLen&&palindrome(c,i,j)) {
maxLen = j-i;
start = i;
}
}
}
return s.substring(start,start+maxLen+1);
}
public boolean palindrome(char c[],int left,int right) {
while(left<right) {
if(c[left++]!=c[right--])
return false;
}
return true;
}
2.中心扩散法
不同于暴力**法是向右的扩散,中心扩散法是以一个或两个字符为中心向它的两边进行扩散,因为此方法只需要两层循环,所以时间复杂度是O(n的2次方)。【要注意的是中心可能是一个字符也有可能是二个字符,如:abccba】
public String longestPalindrome(String s) {
int len = s.length();
if(len<2)
return s;
char c[] = s.toCharArray();
int maxLen = 0;
int start = 0;
for(int i=0;i<len-1;i++) {
int odd = expandFC(c,i,i); //中心为一个字符
int even = expandFC(c,i,i+1); //中心为两个字符
odd = odd>even?odd:even;
if(odd>maxLen) {
maxLen = odd;
start = i - odd/2;
}
}
//需要加1是因为substring函数它的计算规则。如取第零位数是s.substring(0,0+1);
return s.substring(start,start+maxLen+1);
}
public int expandFC(char c[],int left,int right) {
while(left>=0&&right<c.length) {
if(c[left]!=c[right])
break;
left--;
right++;
}
return (right-1) - (left+1);
}
3.动态规划
判断一个字符串是否为回文可以分解成,判断字符串的首尾是否是相等,然后首尾中的子串是否是回文的。所以dp[i][j] = Si==Sj and dp[i+1][j-1](其中的Si和Sj表示的是首尾,dp[i+1][j-1]表示的是首尾中的子串),有时i+1和j-1等于同一个值位置时可以不需要判断这个子串,状态转移公式就可以改成:dp[i][j] = Si= =Sj and (j-i<3 or dp[i+1][j-1])
然后建表填表,注意通过状态转移公式可以看出填表的方向,应该是从先从上到下,然后从左到向,一列一列的去填写。
动态规划中包含三个重要的概念:【最优子结构】【边界】【状态转移公式】。
总结:
不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。
public static String longestPalindrome(String s) {
boolean DP[][] = new boolean[s.length()][s.length()];
int maxLen = 0;
int start = 0;
for(int i=0;i<s.length();i++)
DP[i][i] = true;
//循环是顺序是遵循一列一列的填写
for(int j=1;j<s.length();j++) {
for(int i=0;i<j;i++) {
if(s.charAt(i)!=s.charAt(j))
DP[i][j] = false;
else {
if(j-i<3)
DP[i][j] = true;
else
DP[i][j] = DP[i+1][j-1];
}
if(DP[i][j]&&j-i+1>maxLen) {
maxLen = j-i;
start = i;
}
}
}
return s.substring(start,start+maxLen+1);
}
上一篇: 用批处理解决数学问题的代码第1/4页
下一篇: 写简单的mvc框架实例讲解
推荐阅读
-
python实现对求解最长回文子串的动态规划算法
-
Leetcode刷题记录——面试题48. 最长不含重复字符的子字符串
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划
-
【Hard 递归 动态规划 回文串15】LeetCode 730. Count Different Palindromic Subsequences
-
Leetcode 剑指 Offer 48. 最长不含重复字符的子字符串
-
leetcode 5.最长回文子串(中等,动态规划)
-
中等- LeetCode 5.最长回文子串
-
最长回文子串 LeetCode
-
leetcode最长回文子串
-
LeetCode:最长回文子串