20200829-214.shortest-palindrome.md

214.shortest-palindrome

题目链接：https://leetcode-cn.com/problems/shortest-palindrome/

参考链接：

https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/

https://leetcode-cn.com/problems/shortest-palindrome/solution/shuang-zhi-zhen-by-ni-da-ye-huan-shi-ni-da-ye/

https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-pan-pan-4d/

题目

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

示例 1 :

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

示例 2 :

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

解题

思路[1]最长回文串

• 寻找最长回文串，然后，剩余的字符串倒序拼接到最前面

代码

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
  let [left, right] = [0, s.length - 1];
  let rightIndex = right;
  while(left < right){
    if (s[left] === s[right]) {
      left++
      right--;
    } else {
      left = 0;
      right = --rightIndex;
    }
  }
  return s.slice(rightIndex + 1).split('').reverse().join('').concat(s);
};

思路[2]前后缀比较

• 将字符串s反转后得到的反转字符串s1，拼接s和s1，一定会得到一个回文串
• 如果s的前n位和s1的后n位相同，那么就可以合并起来，即，共同部分时候不需要反转的字符串
• 找到这个最长的公共字符串，然后拼接

代码

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
  let n = s.length;
  let revs = s.split('').reverse().join('');
  for (let i = 0; i < n; i++) {
    if (s.substr(0, n - i) == revs.substr(i))
      return revs.substr(0, i) + s;
  }
  return "";
};

思考

• 还有一种KMP算法，详见https://leetcode-cn.com/problems/implement-strstr/
• 将s视为模版串，他的反转视为查询串，进行KMP匹配，当匹配结束后，如果匹配到 s中的第 i个字符，就说明前i个字符相同，根据思路2，可得结果