Leetcode 214.最短回文串
2024-09-08 11:41:48
最短回文串
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:
输入: "abcd"
输出: "dcbabcd"
这个题目是在字符串前面加字符构成一个最短的回文字符串。我们分析题意,就是找到从第一个字母起始的最长的回文字符串,然后把剩下的倒置加到前面,就得到了最短的回文字符串。怎么找到以第一个字母为起始的最长的回文串,我们可以把s转置,然后找到匹配转置后的字符串从原始字符串第一个开始位置能够匹配的最大长度。这时候我们可以考虑到使用KMP算法,因为KMP算法就是从目标字符串的第一个字母开始匹配。我们可以这么做
S+"#"+S.reverse 然后使用KMP算法
class Solution{
public String shortestPalindrome(String s){
String tmp=s+"#"+new StringBuilder(s).reverse().toString();
int[] table=getTable(tmp);
return new StringBuilder(s.substring(table[table.length-1])).reverse().toString()+s;
}
//KMP求next数组
public int[] getTable(String s){
int len=s.length();
int[] table=new int[len];
char[] a=s.toCharArray();
for(int i=1,k=0;i<len;i++){
while(k>0&&a[i]!=a[k]){
k=table[k-1];
}
if(a[i]==a[k]) k++;
table[i]=k;
}
return table;
}
}
最新文章
- javaScript里的原型链
- Sublime Text3使用记录
- yiic 数据库迁移工具
- EF+WCF怎样更新数据?
- 动态规划(状态压缩):BZOJ 2621 [Usaco2012 Mar]Cows in a Skyscraper
- Java 8 中新的 Date 和 Time 类入门详解
- Python序列的方法(转)
- Java分形
- 关于Elasticsearch 使用 MatchPhrase搜索的一些坑
- GenericServlet 、Servlet和httpServler
- Unity添加多个可视镜头Preview功能(二)
- python kafka
- jsr-303 参数校验—自定义校验注解
- freeswitch控制台日志级别设置以及存储
- 2018-2019-2 20165212 《网络对抗技术》Exp3 免杀原理与实践
- 从云端到边缘 AI推动FPGA应用拓展
- js面试题之求数组最值
- Visual Studio中Debug和Release的区别
- Java银行家算法
- vivo面试学习3(git和svn的区别)
热门文章
- 题解报告:hdu 2030 汉字统计
- 加密解密(1)HTTPS与HTTP区别
- Android系统的启动流程
- Codeforces Beta Round #98 (Div. 2)(A-E)
- html5的表单元素总结
- css中display设置为table、table-row、table-cell后的作用及其注意点
- git push失败the remote end hung up unexpectedly
- HTML5——loading
- ALTER OPERATOR CLASS - 修改一个操作符表的定义
- $(";[lay-id=&#39;";+this.id+";&#39;]";)