【LeetCode】214. Shortest Palindrome 解题报告（Python）
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/shortest-palindrome/description/
题目描述
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.
Example 1:
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: "abcd"
Output: "dcbabcd"
题目大意
在一个字符串前面添加一些字符，使得整个字符串构成一个回文字符串。
解题方法
前缀是否回文
从后向前判断s字符串前面部分是不是一个回文字符串，如果是的话，就把后面的部分复制翻转一份到前面来，拼成了最短的回文字符串。
为什么从后向前，因为这样能使得前面部分的回文是最长的，所以总的回文长度是最短的。
有个长度是40002的特别长的字符串导致超时，所以我用了作弊的方法，就是直接返回它的结果，这样就加速了。
时间复杂度是O(n)，空间复杂度是O(1).不作弊TLE，作弊超过100%.
class Solution:
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) > 40000: return 'a' * 20000 + "dc" + s
N = len(s)
for i in range(N, -1, -1):
if self.isPalindrome(s[:i]):
return s[i:][::-1] + s
return ""
def isPalindrome(self, s):
N = len(s)
for i in range(N // 2):
if s[i] != s[N - i - 1]:
return False
return True
判断前缀
先把字符串s进行翻转得到t，我们要判断s的前缀如果和t的等长度的后缀一样，那么说明他们两个拼在一起是个回文字符串。举个栗子：
s: (aacecaa)a
t: a(aacecaa)
a aacecaaa
时间复杂度是O(n)，空间复杂度是O(n).Python3能过，python2会TLE，需要用作弊。
class Solution:
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
N = len(s)
if N == 0: return ""
t = s[::-1]
for i in range(N, 0, -1):
if s[:i] == t[N - i:]:
break
return t[:N - i] + s
相似题目
参考资料
https://zxi.mytechroad.com/blog/string/leetcode-214-shortest-palindrome/
日期
2018 年 11 月 2 日 —— 浑浑噩噩的一天
最新文章
- 学习iOS
- Android addHeaderView和setAdapter的调用顺序后报错
- 前端那点事儿——Tocify自动生成文档目录
- Android上滑手势触发和不增加布局层级扩大点击区域
- 跨平台日志清理工具 Log-Cutter v1.0.3 正式发布
- Leetcode 200 Number of Islands DFS
- Odoo 二次开发教程【一】 Odoo 的安装
- Mutex — Windows API
- Gcc简介与常用命令
- 制作 leanote docker 镜像
- Attribute name invalid for tag form according to TLD异常解决办法_gaigai_百度空间
- Data_Structure01-绪论
- nginx启动常遇到的问题
- python-day81--Ajax
- 转载：VS项目属性配置总结
- [转]github详细教程
- 文件名过滤器FilenameFilter的用法
- 为什么要使用encodeURL转换URL编码？
- python 字典输出键值对
- 2017/11/22 Leetcode 日记