注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex5 Longest Palindromic Substring  

2015-05-21 22:16:17|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这个题挺难的,开始想的是两边夹的方法,也就是palindromic的string,首尾肯定是相同的,然后一直往内递推,一旦遇不一样的,说明不回文。但是这个是有问题的 比如aaabaaaa就过不去。后来看网上的说法,有两种解法
第一种,相当于s和他的逆转字符求解lcs,是n^2复杂度的,oj不让过。所以就没有意义了,不过还是有其他用动态规划的算法让过了,不知道为什么lcs就是不让过。
下面算法的说明  
---------------------------------------------------------------------------------------------------------------------------------------------------------
动态规划,类似于lcs的解法,数组flag[i][j]记录s从i到j是不是回文

首先初始化,i>=j时,flag[i][j]=true,这是因为s[i][i]是单字符的回文,当i>j时,为true,是因为有可能出现flag[2][1]这种情况,比如bcaa,当计算s从2到3的时候,s[2]==s[3],这时就要计算s[2+1] ?= s[3-1],总的来说,当i>j时置为true,就是为了考虑j=i+1这种情况。

接着比较s[i] ?= s[j],如果成立,那么flag[i][j] = flag[i+1][j-1],否则直接flag[i][j]=false
---------------------------------------------------------------------------------------------------------------------------------------------------------

class Solution {
public:
string longestPalindrome(string s) {
int len = s.length(), max = 1, ss = 0, tt = 0;
bool flag[len][len];
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
if (i >= j)
flag[i][j] = true;
else flag[i][j] = false;
for (int j = 1; j < len; j++)
for (int i = 0; i < j; i++)
{
if (s[i] == s[j])
{
flag[i][j] = flag[i+1][j-1];
if (flag[i][j] == true && j - i + 1 > max)
{
max = j - i + 1;
ss = i;
tt = j;
}
}
else flag[i][j] = false;
}
return s.substr(ss, max);
}
};

上面是原作者写的,不过貌似不是说的很清楚为什么i>j的时候要是True,另一个作者写到当s[i]=s[j]的时候,是单个回文字符串,而如果是两个字符,也就是i+1 = j的时候,必须有s[i] =s[i+1]才能判断是true,也就是判断上三角矩阵,再加一斜行才能够判定。这里作者给了一个类似的思路,但是比上面一个讲的清楚,我画了一张图,见下图
ex5 Longest Palindromic Substring - HT - HT·生活
 
 
分为第一类对角点,他们自动确定为true,而对第二类对角点需要判定一下,然后这两类对角点,向右上角扩展,复杂复杂度是n^2的


string longestPalindrome(string s) {

size_t n = s.length();
bool **dp = new bool*[n];
for (size_t i = 0; i < n; ++i)
{
dp[i] = new bool[n];
}

//为基准情况赋值
int startPos = 0;
int max = 1;
for (size_t i = 0; i < n; ++i)
{
dp[i][i] = true;
if (i + 1 < n)
{
if (s[i] == s[i+1])
{
dp[i][i+1] = true;
startPos = i;
max = 2;
}
else dp[i][i+1] = false;
}
}

//动规求解,前面已求len = 1, len = 2的情况
for (int len = 3; len <= n; ++len)
{
for (int i = 0; i < n - len + 1; ++i)
{
int j = i + len - 1;

if (dp[i+1][j-1] && s[i] == s[j])
{
dp[i][j] = true;
int curLen = j - i + 1;
if (curLen > max)
{
startPos = i;
max = curLen;
}
}
else dp[i][j] = false;

}
}

//释放二维数组
for (size_t i = 0; i < n; ++i)
delete[] dp[i];

delete[] dp;
return s.substr(startPos,max);
}





看到网上有人讲的一个线性算法,吊炸天,Manacher’s Algorithm,大概明白其意思,表示不知道怎么推啊~~参考中第三个是讲的最好的,推导就不推导了。贴一下代码

class Solution {
public:
string longestPalindrome(string s) {
//http://blog.csdn.net/hopeztm/article/details/7932245
int len = s.size();
if (len <= 1)
return s;

string T = preProcess(s);
//cout << T << endl;

len = T.size();
int C = 0, R = 0; //就是那几个恶心的值
vector<int> P(len,0);


int i_mirror = 0;
int i, j;
for (i = 0; i < len; i++)
cout << P[i] << " ";
for (i = 1; i < len - 1; i++)
{
i_mirror = 2 * C - i;//计算i'这个东西

if (R > i)
{
P[i] = myMin(R-i,P[i_mirror]);
}
else
{
P[i] = 0;
}
//扩充在i位置后面的P[i]

while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
{
P[i] =P[i] +1; //因为是对称的
//cout << P[i] << endl;
}
if (i + P[i] > R) //超过了R,就需要更新C和R
{
C = i;
R = i + P[i];
}
}
int maxLen = 0;
int centerIndex = 0;
for (i = 0; i < len; i++)
{
if (P[i]>maxLen)
{
maxLen = P[i];
centerIndex = i;
}
}
string result = s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
return result;
}
int myMin(int a,int b)
{
return a > b ? b : a;
}
string preProcess(string s)
{
int n = s.length();
if (n == 0) return "";
string ret="^"; //这样就不用进行边界检查了
for (int i = 0; i < n; i++)
{
ret.append("#" + s.substr(i, 1));
}

ret.append("#$"); //这样就不用进行边界检查了
return ret;
}
string LCS(string s1, string s2)
{
int len1 = s1.size();
int len2 = s2.size();
vector<int>mark(len2 + 1, 0);
int i, j;
//for (i = 0; i < mark.size(); i++)
// cout << mark[i] << " ";
//cout << endl;

int max = 0;
int pe = 0;
for (i = 1; i < len1; i++)
{
for (j = len2; j > 0; j--)
{
if (s1[i] == s2[j - 1])
{
mark[j] = mark[j - 1] + 1;
}
else
{
mark[j] = 0;
}
if (mark[j] > max)
{
max = mark[j];
pe = i;
}
}
}
string result;
i = 0;
j = pe - max + 1;
while (i < max)
{
result.push_back(s1[j]);
j++;
i++;
}
//cout << endl << max << endl;
return result;
}
};






参考
http://blog.csdn.net/hopeztm/article/details/7932245
http://blog.csdn.net/feliciafay/article/details/16984031
http://blog.csdn.net/hopeztm/article/details/7932245
http://www.cnblogs.com/daoluanxiaozi/p/longest-palindromic-substring.html
  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017