214.最短回文串

链接：214.最短回文串
难度：Hard
标签：字符串、字符串匹配、哈希函数、滚动哈希
简介：给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

题解 1 - typescript

• 编辑时间：2020-08-29
• 执行用时：1164ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：通过判断每个子串是否为回文，如果是则添加后续字串。

function shortestPalindrome(s: string): string {
  if (isPalindrome(s)) return s;
  for (let i = s.length - 1; i >= 0; i--) {
    const subS = s.substring(0, i);
    if (!isPalindrome(subS)) continue;
    return s.substr(i).split('').reverse().join('') + s;
  }
  return '';
  function isPalindrome(s: string) {
    let l = 0;
    let r = s.length - 1;
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  }
}

题解 2 - typescript

• 编辑时间：2021-10-15
• 执行用时：68ms
• 内存消耗：44.4MB
• 编程语言：typescript
• 解法介绍：kmp。

function shortestPalindrome(s: string): string {
  const n = s.length;
  let str = s + '#';
  for (let i = n - 1; i >= 0; i--) str += s[i];
  const next = [-1];
  for (let i = 1, j = -1; i < n * 2 + 1; i++) {
    while (j !== -1 && str[j + 1] !== str[i]) j = next[j];
    if (str[j + 1] === str[i]) j++;
    next[i] = j;
  }
  const idx = next[2 * n];
  let ans = s;
  for (let i = Math.max(0, idx + 1); i < n; i++) ans = s[i] + ans;
  return ans;
}