【网易互联网笔试编程题】小易爱回文 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

相关文章

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

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思路代码实现代码解释复杂度分析三、