Shortest Palindrome 两题

在此给出两道与 Shortest Palindrome 主题相关的解题报告。相关题目:

  1. Shortest Palindrome | LeetCode OJ
  2. TopCoder Statistics - Problem Statement

后者可视为前者的 follow up。

Leetcode 214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Credits: Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

$O(n^2)$ solution is trivial, let's talk about the $O(n)$ solution.

经典的思路是把问题转化成一个 String Matching 问题:设输入的字符串为 $S$,设 $S'$ 为 $S$ 反转(reversed)后的字符串,求 maximum $k$ such that $S_k \sqsupset S'$。$S_k$ is the $k$-characters prefix of $S$. $S_k \sqsupset S'$ states that $S_k$ is a suffix of $S'$.

由此,该问题可以直接通过 KMP 求解,以下为实现代码:

class Solution {  
 public:
  string shortestPalindrome(string s) {
    const int n = s.size();
    vector<int> pi(n + 1, 0);
    int k = 0;
    for (int i = 1; i < n; ++i) {
      while (k > 0 && s[k] != s[i]) {
        k = pi[k];
      }
      if (s[k] == s[i]) {
        ++k;
      }
      pi[i + 1] = k;
    }

    auto rs = s;
    reverse(rs.begin(), rs.end());
    k = 0;
    for (int i = 0; i < n; ++i) {
      while (k > 0 && rs[i] != s[k]) {
        k = pi[k];
      }
      if (rs[i] == s[k]) {
        ++k;
      }
    }
    return rs.substr(0, n - k) + s;
  }
};

SRM 165 Div 2, ShortPalindromes

Problem Statement

A palindrome is a string that is spelled the same forward and backwards. Given a string base that may or may not be a palindrome, we can always force base to be a palindrome by adding letters to it. For example, given the word "RACE", we could add the letters "CAR" to its back to get "RACECAR" (quotes for clarity only). However, we are not restricted to adding letters at the back. For example, we could also add the letters "ECA" to the front to get "ECARACE". In fact, we can add letters anywhere in the word, so we could also get "ERCACRE" by adding an 'E' at the beginning, a 'C' after the 'R', and another 'R' before the final 'E'. Your task is to make base into a palindrome by adding as few letters as possible and return the resulting string. When there is more than one palindrome of minimal length that can be made, return the lexicographically earliest (that is, the one that occurs first in alphabetical order).

注意到 Leetcode 214. Shortest Palindrome 要求的是把字符添加到 $S$ 的前方(by adding characters in front of it),而 SRM 165 Div 2,ShortPalindromes 的要求是把字符添加到 $S$ 中的任意位置。

TopCoder Statistics 简洁明了地给出了解题思路,直接 DP 即可,在此不做重复叙述。以下是实现代码:

class ShortPalindromes {  
 public:
  string shortest(string base) {
    const int n = base.size();
    vector<vector<string>> dp(n, vector<string>(n));
    // init.
    for (int i = 0; i < n; ++i) {
      dp[i][i] = base[i];
    }
    // dp.
    for (int size = 2; size <= n; ++size) {
      for (int i = 0; i + size <= n; ++i) {
        int j = i + size - 1;
        if (base[i] == base[j]) {
          string mid = size > 2? dp[i + 1][j - 1] : "";
          dp[i][j] = base[i] + mid + base[i];
        } else {
          string si = base[i] + dp[i + 1][j] + base[i];
          string sj = base[j] + dp[i][j - 1] + base[j];
          if (si.size() < sj.size()) {
            dp[i][j] = si;
          } else if (sj.size() < si.size()) {
            dp[i][j] = sj;
          } else {
            dp[i][j] = si < sj? si : sj;
          }
        }
      }
    }
    return dp[0][n - 1];
  }
};