一天一大 lee(最短回文串)难度:困难-Day20200829
程序员文章站
2022-05-08 11:26:38
...
题目:
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例
- 示例 1
输入: "aacecaaa"
输出: "aaacecaaa"
- 示例 2
输入: "abcd"
输出: "dcbabcd"
抛砖引玉
思路
最直观想到的思路就是找到从 s 首位开始的最长回文字符串,再讲不是该串的部分颠倒拼接到 s 头部就得到了需要的结果
- s 从 0->s.length 枚举 s 的子串
- 判断枚举的子串是否未回文字符串
- 不是继续枚举
- 是返回 s 中不在该子串部分的颠倒字符+s
其中校验字符串是否为子串在:20200610:回文数 (难度:简单)中就用到过
/**
* @param {string} s
* @return {string}
*/
var shortestPalindrome = function (s) {
let len = s.length
// 从长到短求最长前缀回文字符
for (let i = len; i >= 0; i--) {
let _result = s.substring(0, i)
if (check(_result)) {
return Array.from(s.substring(i, len)).reverse().join('') + s
}
}
// 校验是否为回文字符串
function check(x) {
let str = '' + x
return Array.from(str).reverse().join('') === str
}
}
提交后会发现 119 / 120 个通过测试用例,存在 2 个测试用例没有通过
换种思路
在20200823: 重复的子字符串 (难度:简单)中就用到了 KMP 算法去校验一个模式串是否匹配另外一个匹配串
- 将 s 和 s 字符颠倒 str 两个字符匹配,匹配上的部分则说明在 s 内部本事这两部是回文子串
- 在 KMP 算法中存在求最长公共前缀的逻辑(也是匹配时指针不连续跳转的序列),那么匹配时记录从哪个位置完成了匹配,
则该位置之前的部分都是需要,补充完成才能形成回文字符非部分 - 最后的问题,补充的字符从哪里来呢,从 s 中,但是如果补充的部分字符顺序和 s 中相同则不能形成回文片段,则需要截取 s 的片段颠倒后再拼接
-
实例 1:
s->aacecaaa
str->aaacecaa
match -> 6a a a c e c a a - a a c e c a a - 0 1 2 3 4 5 6 -
实例 2:
s->abcd
str->dcba
match -> 0d c b a - - - a - - - 0
/**
* @param {string} s
* @return {string}
*/
var shortestPalindrome = function (s) {
let len = s.length,
str = s.split('').reverse().join('')
// 正反字符匹配求最长匹配位数
function kmp(query, pattern) {
let fail = Array(len).fill(-1)
// 最长公共前缀,不存在公共前缀填充-1
for (let i = 1; i < len; ++i) {
let j = fail[i - 1]
while (j != -1 && pattern[j + 1] != pattern[i]) {
j = fail[j]
}
if (pattern[j + 1] == pattern[i]) {
fail[i] = j + 1
}
}
// 校验 match记录匹配的位置
let match = -1
for (let i = 0; i < len; ++i) {
// 如果当前不匹配匹配,指针跳跃到前缀位置开始匹配
while (match != -1 && pattern[match + 1] != query[i]) {
match = fail[match]
}
// 如果当前位匹配,逐个向后匹配
if (pattern[match + 1] == query[i]) {
++match
}
}
return match
}
let num = kmp(str, s),
add = num == len - 1 ? '' : s.substring(num + 1)
return Array.from(add).reverse().join('') + s
}
博客: 小书童博客
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言
公号: 坑人的小书童
上一篇: 前端异步编程系列之何为异步编程(1/4)
推荐阅读
-
一天一大 lee(解数独)难度:困难-Day20200915
-
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
-
一天一大 lee(冗余连接 II)难度:困难-Day20200917
-
【一天一大 lee】最大间距 (难度:困难) - Day20201126
-
一天一大 lee(N 皇后)难度:困难-Day20200903
-
【一天一大 lee】N皇后 II (难度:困难) - Day20201017
-
【一天一大 lee】插入区间 (难度:困难) - Day20201104
-
一天一大 lee(24点游戏)难度:困难-Day20200822
-
一天一大 lee(回文对)难度:困难-Day20200806
-
一天一大 lee(最短回文串)难度:困难-Day20200829