Leetcode

Shortest Palindrome

  • Time:O(n^2)
  • Space:O(n)

C++

class Solution {
 public:
  string shortestPalindrome(string s) {
    string t = s;
    reverse(begin(t), end(t));

    const string_view sv_s(s);
    const string_view sv_t(t);

    for (int i = 0; i < s.length(); ++i)
      if (sv_s.substr(0, s.length() - i) == sv_t.substr(i))
        return t.substr(0, i) + s;

    return t + s;
  }
};

JAVA

class Solution {
  public String shortestPalindrome(String s) {
    final String t = new StringBuilder(s).reverse().toString();

    for (int i = 0; i < t.length(); ++i)
      if (s.startsWith(t.substring(i)))
        return t.substring(0, i) + s;

    return t + s;
  }
}

Python

class Solution:
  def shortestPalindrome(self, s: str) -> str:
    t = s[::-1]

    for i in range(len(t)):
      if s.startswith(t[i:]):
        return t[:i] + s

    return t + s