当前位置:网站首页>力扣(LeetCode)214. 打家劫舍 II(2022.08.02)
力扣(LeetCode)214. 打家劫舍 II(2022.08.02)
2022-08-03 06:41:00 【ChaoYue_miku】
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入:s = “aacecaaa”
输出:“aaacecaaa”
示例 2:
输入:s = “abcd”
输出:“dcbabcd”
提示:
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shortest-palindrome
方法一:KMP算法
C++提交内容:
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
vector<int> fail(n, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && s[j + 1] != s[i]) {
j = fail[j];
}
if (s[j + 1] == s[i]) {
fail[i] = j + 1;
}
}
int best = -1;
for (int i = n - 1; i >= 0; --i) {
while (best != -1 && s[best + 1] != s[i]) {
best = fail[best];
}
if (s[best + 1] == s[i]) {
++best;
}
}
string add = (best == n - 1 ? "" : s.substr(best + 1, n));
reverse(add.begin(), add.end());
return add + s;
}
};
边栏推荐
猜你喜欢
随机推荐
【playwright】pytest-playwright增加代理服务选项
c现代方法16章基础
《多线程案例》阻塞队列、定时器、线程池、饿汉与懒汉模式
jvm 面试题
加载properties文件,容器总结
10 分钟彻底理解 Redis 的持久化和主从复制
被数据分析重塑的5个行业
REST学习
9月考,如何选择靠谱正规的培训机构?
学会可视化大屏布局技巧,让领导都赞不绝口
Detailed explanation of cause and effect diagram of test case design method
贷中存量客户的价值挖掘与分类实现,试试这一重要的场景模型
请求与响应:响应
Flink的Exactly-Once、状态机制、watermark机制
信息学奥赛一本通T1454:山峰和山谷
第四章:架构,Architecture
keepalived安装部署
1066 Root of AVL Tree // AVL平衡二叉搜索树模板
【着色器实现Glow可控局部发光效果_Shader效果第十三篇】
C语言入门实战(14):选择排序