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

HT·生活

123

 
 
 

日志

 
 

ex214 Shortest Palindrome  

2015-05-31 17:23:36|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".


我能想到的就是最直接的方法,从头开始找最长的palindrome字符串,把后面截掉,颠倒,补到前面就是结果了。n^2的复杂度,这种方法时间耗费较长

/*
* 第一种方法应该是最简单粗暴的,从字符串头开始,找最长的回文字符串
* 必须以string的头开始,把剩下的逆转过来就可以了
* 复杂度是n^2的
*/
//================================================================
bool isPalindrom(char* s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
++start; --end;
}
return true;
}

char* shortestPalindrome(char* s) {
int pos = strlen(s) - 1;
for (; pos > 0; --pos) {
if (s[pos] == s[0] && isPalindrom(s, 0, pos)) break;
}
char* res = (char*)malloc(2 * strlen(s) - pos);
int idx = 0;
for (int i = strlen(s) - 1; i > pos; --i) res[idx++] = s[i];
strcpy(res + idx, s);
return res;
}
//================================================================

网上介绍了kmp和manacher的方法,我表示对这两个都不是很熟悉,后面需要仔细研究一下

/*
* 第是基于manacher 我表示对这个算法确实不是很熟
*
* 复杂度是O(n)的
*/
class Solution1 {
public:
int longestPalindrom(string s) {
string s1;
s1.resize(2 * s.length() + 2);
int idx = 0;
s1[idx++] = '$';
s1[idx++] = '#';
for (char a : s) {
s1[idx++] = a;
s1[idx++] = '#';
}
vector<int> p(s1.length(), 0);
int res = 0;
for (int id = 0, i = 1; i < s1.length(); ++i) {
if (i < id + p[id]) p[i] = min(p[2 * id - i], id + p[id] - i);
else p[i] = 1;
while (s1[i + p[i]] == s1[i - p[i]]) ++p[i];
if (id + p[id] < i + p[i]) id = i;
if (p[i] == i) res = max(res, i);
}
return res - 1;
}

string shortestPalindrome(string s) {
int pos = longestPalindrom(s);
string res;
for (int i = s.length() - 1; i >= pos; --i) res.push_back(s[i]);
return res + s;
}
};
/*
* 第是基于kmp的 我表示对这个算法也不是很熟
*
* 复杂度是O(n)的
*/
class Solution {
public:
string shortestPalindrome(string s) {
string rev_s = s;
reverse(rev_s.begin(), rev_s.end());
string l = s + "#" + rev_s;

vector<int> p(l.size(), 0);
for (int i = 1; i < l.size(); i++) {
int j = p[i - 1];
while (j > 0 && l[i] != l[j])
j = p[j - 1];
p[i] = (j += l[i] == l[j]);
}

return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
}
};

参考
https://leetcode.com/discuss/36807/c-8-ms-kmp-based-o-n-time-%26-o-n-memory-solution
http://www.cnblogs.com/easonliu/p/4522724.html
  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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