Longest Palindromic Substring
Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic
substring.
对于这道题,要怎么设计这个table就是非常难想到的事情。因为要利用一个二维数组,把二维数组的两个下标作为标示主串里面的两个字符位置,实在是够难想到的了。
什么时候使用动态规划法:
• Optimal substructure
• Overlapping subproblems
构建解的方法:
Characterize structure of optimal solution
Recursively define value of optimal solution
Compute in a bottom-up manner
如果是用暴力法的话,就需要O(n^3) 时间效率了,但是使用动态规划法,就只需要O(n^2)的时间复杂度了。
最难想的地方:P代表一个表,比较难想的就是P表的下标i和j代表原字符串中的两个前后下标s[i]和s[j]的位置。
如果P[i,j]为真,当且仅当si-1,si-2...sj-1,sj这一个子串都为palindrome。例如:s[] = skrdjdre那么P[2][6] = true,因为s[2]=r=s[6],且djd为回文。
不明白,可以看下表,动手填一填,未填出的都初始化为false,其中t代表填写true:
2014-1-24 Update
Leetcode有更新了,增加了两个大数据测试,一般使用vector容器的动态规划法超时了,而且也禁止了使用二维数组,会报错memory limit exceeded。
所以更新下动态规划法,使用3个一维数组,测试通过,不过时间大概为836ms,还是最下面的两边扩展计算的解法最优了。
class Solution {
public:
string longestPalindrome(string s)
{
int index = 0, len = 1;
int table[3][1000] = {1};
int last = -1; int cur = 1;
for (int i = 0; i < s.length(); i++)
{
table[0][i] = 1;
}
for (int i = 1; i < s.length(); i++)
{
if (s[i] == s[i-1])
{
table[cur][i] = 2;
index = i-1;
len = 2;
}
else table[cur][i] = 0;
}
for (int d = 2; d < s.length(); d++)
{
cur = (cur+1)%3; last = (last+1)%3;
for (int i = 0, j = d; j < s.length(); i++, j++)
{
if (s[i] == s[j] && table[last][j-1] != 0)
{
table[cur][j] = table[last][j-1]+2;
if (table[cur][j] > len)
{
len = table[cur][j];
index = i;
}
}
else table[cur][j] = 0;
}
}
return s.substr(index, len);
}
};
下面就是实现上述思想的程序,时间复杂度O(n*n),空间复杂度O(n*n)
string longestPalindrome(string s)
{
int n = s.length();
vector<vector<bool> > table;
vector<bool> temp(n, false);
for (int i = 0; i < n; i++)
{
table.push_back(temp);
table[i][i] = true;
}
//Attention: Don't forget we need two centor for palindrome
int subStartPoint = 0;
int maxLength = 1;
for (int i = 1; i < n; i++)
{
if (s[i-1] == s[i])
{
table[i-1][i] = true;
subStartPoint = i-1;
maxLength = 2;
}
}//for
for (int k = 3; k <= n; k++)
{
for (int i = 0; i <= n-k; i++)
{
int j=k+i-1;
if (s[i] == s[j] && table[i+1][j-1] == true)
{
table[i][j] = true;
if(maxLength < k)
{
subStartPoint = i;
maxLength = k;
}
}
}//for(int i = 0...
}//for(k=3...
return s.substr(subStartPoint, maxLength);
}
实际leetcode运行速度:
但是其实有更加简单的方法,实际运行速度更加快。
思想:
1. 以每个s[i]字符为中心,两边测试看以这个字符为中心的回文长度是多少
2. 以每两个字符s[i-1]s[i]为中心,测试这两个字符是否相等,和以这两个字符为中心的回文有多长
最后记录最大长度和最大长度子串起点
其实我觉得这个算法比前面的算法还好理解:
int testTwoSides(string &s, int low, int up)
{
int n = s.length();
int max = 0;
if (low == up)
{
low--;
up++;
max = 1;
}
while (low>=0 && up<n && s[low] == s[up])
{
max+=2;
low--;
up++;
}
return max;
}
string longestPalindrome(string s)
{
int n = s.length();
int subStartPoint = 0;
int maxLength = 1;
int temp = 0;
for (int i = 0; i < n; i++)
{
temp = testTwoSides(s, i, i);
if (temp > maxLength)
{
subStartPoint = i - temp/2;
maxLength = temp;
}
}
for (int i = 1; i < n; i++)
{
temp = testTwoSides(s, i-1, i);
if (temp > maxLength)
{
subStartPoint = i - temp/2;
maxLength = temp;
}
}
return s.substr(subStartPoint, maxLength);
}
理论上这个算法的时间复杂度是O(n*n),空间复杂度O(1);
记得前段时间看到某博主对于类似的这样的算法说成时间复杂度是O(n),所以明确说明这个时间复杂度是:O(n*n)
计算起来有点麻烦,至于是如何计算的,因为牵涉单概率论的知识和算法时间复杂度计算基础知识,虽然不算很难的概率论知识,但是不是那么容易讲明白的。怕讲不好,而且也不用那么麻烦每个算法都那么正规的分析,不然就累死人额。
所以可以对于这个算法可以给出特定例子走一走,比如对于串aaaaaaaaaaa,那么它就是最坏情况的时间复杂了。
实际运行效果却是出奇的好:
2013/12/7 update:
上面的算法其实可以利用一个循环就可以了,不需要多一个循环,不过时间效率一样。应该可以稍微优化一点吧。
class Solution {
public:
string longestPalindrome(string &s)
{
int startPoint = 0;
int maxLen = 1;
for (int j = 1; j < s.length(); j++)
{
int t = testTwoSides(s, j, j);
if (t > maxLen)
{
startPoint = j - t/2;
maxLen = t;
}
t = testTwoSides(s, j-1, j);
if (t > maxLen)
{
startPoint = j - t/2;
maxLen = t;
}
}
return s.substr(startPoint, maxLen);
}
int testTwoSides(string &s, int low, int up)
{
int n = s.length();
int max = 0;
if (low == up)
{
low--;
up++;
max = 1;
}
while (low>=0 && up<n && s[low] == s[up])
{
max+=2;
low--;
up++;
}
return max;
}
};
leetCode网站上的分析的不错了:
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
分享到:
相关推荐
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
title: "[0516] 最长回文子序列"题目描述给定一个字符串s,找到其中最长的回文子序列。示例 1:输入:输出:一个可能的最长回文子序列为 "bbbb
c# c#_Leetcode面试题解之第8题字符串转整数
java_leetcode面试题解之第8题字符串转换整数atoi
python python_leetcode面试题解之第43题字符串相乘_题解
730. 统计不同回文子字符串 给定一个字符串 S,找出 S 中不同的非空回文子序列个数,并返回该数字与 10^9 + 7 的模。 通过从 S 中删除 0 个或多个字符来获得子字符序列。 如果一个字符序列与它反转后的字符序列一致...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 示例 2: ...
LeetCode Longest Common Prefix解决方案
c++ c++_c++编程基础之leetcode题解第28题找出字符串第一个匹配项的下标
LeetCode 205的题目是“同构字符串”(Isomorphic Strings),要求判断两个字符串是否是同构的。如果字符串s可以通过字符替换得到字符串t,那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
1、将字母按照数量从小到大排序 2、如果连续放置了两个最多的字母,就考虑放置一个次大的字母 3、否则,能放置最大的字母,就放置最大的字母 4、其他情况,没有字母
leetcode 答案最长子串 来自 leetcode.com 的问题。 描述: 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为3。
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)...
Leetcode 1312. 让字符串成为回文串的最少插入次数问题描述1312. 让字符串成为回文串的最少插入次数 - 力扣(LeetCode)算法解法1: 递
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。示例 1:示例 2:第一版var isPalindrome = function