欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一天一大 lee(最短回文串)难度:困难-Day20200829

程序员文章站 2022-05-08 11:26:38
...

一天一大 lee(最短回文串)难度:困难-Day20200829

题目:

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

示例

  1. 示例 1
输入: "aacecaaa"
输出: "aaacecaaa"
  1. 示例 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 个测试用例没有通过

一天一大 lee(最短回文串)难度:困难-Day20200829

换种思路

20200823: 重复的子字符串 (难度:简单)中就用到了 KMP 算法去校验一个模式串是否匹配另外一个匹配串

  • 将 s 和 s 字符颠倒 str 两个字符匹配,匹配上的部分则说明在 s 内部本事这两部是回文子串
  • 在 KMP 算法中存在求最长公共前缀的逻辑(也是匹配时指针不连续跳转的序列),那么匹配时记录从哪个位置完成了匹配,
    则该位置之前的部分都是需要,补充完成才能形成回文字符非部分
  • 最后的问题,补充的字符从哪里来呢,从 s 中,但是如果补充的部分字符顺序和 s 中相同则不能形成回文片段,则需要截取 s 的片段颠倒后再拼接

一天一大 lee(最短回文串)难度:困难-Day20200829

  1. 实例 1:
    s->aacecaaa
    str->aaacecaa
    match -> 6

    a a a c e c a a
    - a a c e c a a
    - 0 1 2 3 4 5 6
  2. 实例 2:
    s->abcd
    str->dcba
    match -> 0

    d 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 栏目
欢迎关注留言

公号: 坑人的小书童

一天一大 lee(最短回文串)难度:困难-Day20200829