当前位置:网站首页>力扣(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;
}
};
边栏推荐
猜你喜欢
随机推荐
HCIP笔记整理 2022/7/18
excel高级绘图技巧100讲(二十一)- Excel层叠柱形图
【Shell】3万字图文讲解带你快速掌握shell脚本编程
2022用户画像构建
(十五)51单片机——呼吸灯与直流电机调速(PWM)
ISIJ 2022收官,中国初中生再展风采
信息学奥赛一本通T1454:山峰和山谷
MySQL - 视图操作
调用feign报错openfeign/feign-core/10.4.0/feign-core-10.4.0.jar
关于任命韩文弢博士代理NOI科学委员会主席的公告
解决登录vCenter提示“当前网站安全证书不受信任“
分治法求解中位数
Detailed explanation of cause and effect diagram of test case design method
重量级大咖来袭:阿里云生命科学与智能计算峰会精彩内容剧透
Detailed explanation and reproduction of AlexNet network
Example of embedding code for continuous features
【图像去噪】基于matlab稀疏表示KSVD图像去噪【含Matlab源码 2016期】
神经网络原理及代码实现
hashSet解析
华为设备配置BFD状态与接口状态联动