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

题目:

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

示例

1. 示例 1

输入: "aacecaaa"
输出: "aaacecaaa"

2. 示例 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. 实例 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 栏目
欢迎关注留言

公号: 坑人的小书童