【网易互联网笔试编程题】小易爱回文 LeetCode 214. 最短回文串(回顾 KMP 和 马拉车算法)

本文主要是介绍【网易互联网笔试编程题】小易爱回文 LeetCode 214. 最短回文串(回顾 KMP 和 马拉车算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

样例

输入: "aacecaaa"
输出: "aaacecaaa"输入: "abcd"
输出: "dcbabcd"

暴力解法(未通过)

根据问题,我们只能在字符串的开头插入字符。因此,我们可以从字符串开头找到最大的回文子串,然后反转剩余的子串并附加到开头。这必然是正确的答案,因为不可能通过在开头插入字符来得到更短的回文。

可能题库那道题更新了数据,原本官方题解暴力是能过的,但现在暴力最后一个 case 过不了,果断放弃寻找其它方法。

class Solution {
public:string shortestPalindrome(string str) {string s = str;reverse(s.begin(),s.end());int n = str.size();string res="";int j=0;for(int i=0;i<n;i++){if(str.substr(0,n-i) == s.substr(i)){j=i;break;}}res+=s.substr(0,j);res+=str;return res;}
};

优化:双指针与递归结合(通过)

在之前暴力方法中,我们通过子字符串匹配的方式来找到了最长回文子串,但每次都检查完整的子字符串,这显然不是很高效。

于是我们可以通过双指针的方式来找到我们包含最长回文子串的字符串,注意!是包含最长回文子串。当然,最好的情况是能直接找到最长回文子串。

正确性证明如下:若字符串全部为回文,则 i 会自增 n 次。若结尾有其他字符,i 会自增回文子串的长度。于是,即使 [0,i) 并不总是紧界,但它总包含从开头开始的最长回文子串。(摘自@官方题解)

那我们还是按照暴力解法的思路,由于是在字符串前面添加字符,那么必然从开头开始能够找到一个最长回文子串,然后将字符串剩下部分反转然后添加到前面即可。

在下面代码中,我们通过双指针找到了包含最长回文子串的字符串,然后不断递归,直到从中提取到最长回文子串,然后进行字符串拼接:

最短回文串结果集 = 原字符串剩下部分的反转 + 最长回文子串 + 原字符串剩下部分

class Solution {
public:string shortestPalindrome(string s) {int n = s.size();int i=0;for(int j=n-1;j>=0;j--)if(s[i] == s[j]) i++;if(i==n) return s;string revs = s.substr(i);reverse(revs.begin(),revs.end());return revs + shortestPalindrome(s.substr(0,i)) + s.substr(i);}
};

KMP 建立部分匹配表(通过)

在暴力解法中,我们反转了原始字符串 str 并存储为 s。然后从 0 到 n−1 迭代 i,判断

str.substr(0,n-i) == s.substr(i)

这条语句其实就是找到与后缀相同的最长前缀,而 KMP的核心——部分匹配表正是"前缀"和"后缀"的最长的共有元素的长度。

那么,我们将原字符串首先进行反转,然后创建新字符 ans = s + "@" + reverse(s),并使用该字符串进行部分匹配表生成(其中中间字符除字母外可随意,但是必须要有)

如果没有@,两个字符串可能会发生混淆,造成错误的答案。举例而言,字符串 “aaaa”。如果不在中间插入 "@",新字符串会是 “aaaaaaaa”, 最长前缀大小会成为 7,这显然是错的。因此,中间的分隔符是必要的。

最后,我们只需要返回最大回文子串后的子串的反转(长度为 n - f [拼接后的字符串的长度-1] )+ 原字符串 ss

class Solution {
public:string shortestPalindrome(string s) {int len = s.size();string rvs = s;reverse(rvs.begin(),rvs.end());string ans = s +"@"+ rvs;int n = ans.size();vector<int> f(n,0);for(int i=1;i<n;i++){int t = f[i-1];while(t && ans[i]!= ans[t]) t = f[t-1];if(ans[i] == ans[t]) t++;f[i] = t;}return rvs.substr(0,len-f[n-1]) + s;}
};

Manacher算法 (马拉车)

我们知道,马拉车可以求出最长回文子串,我不知道是 leetcode不支持 string直接判断相等还是咋的。一直有如下报错,马拉车也应该没有写错。


样例本地测试可以过的,先写到这里吧,如果有小伙伴知道是什么问题可以告诉我一下,我立即修改,谢谢~

#include<bits/stdc++.h>
using namespace std;
int manacher(string s){string tmp = "@";for(int i=0;i<s.size();i++){tmp+="#";tmp+=s[i];}tmp+="#";tmp+="@";int n = 2*s.size()+1;vector<int> len(n,0);int po =0 , mx =0 , ans=-1;for(int i=1;i<=n;i++){int j = 2*po - i;if(i<mx)len[i] = min(len[j],mx-i);elselen[i] = 1;while(tmp[i+len[i]] == tmp[i-len[i]]) len[i]++;if(i+len[i] > mx){mx = i+len[i];po = i;}ans = max(ans,len[i]);}return ans-1;
}
string shortestPalindrome(string s) {int mxlen = manacher(s);string rvs = s.substr(mxlen);reverse(rvs.begin(),rvs.end());return rvs + s;
}
int main(){string str;while(cin>>str){string res = shortestPalindrome(str);cout<<res<<endl;}return 0;
}

最后

每篇文章制作不易,养成一个阅读好习惯,觉得不错,反手就是一个赞,这样我也能发现你啦~

另外,Github 已经为前端小伙伴整理了一份完整地笔记,已获100+ star,别错过哟!

小狮子前端笔记仓库传送门

学如逆水行舟,不进则退!我们下期再见!

这篇关于【网易互联网笔试编程题】小易爱回文 LeetCode 214. 最短回文串(回顾 KMP 和 马拉车算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/262742

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1