Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

214. Shortest Palindrome

Time: $O(n^2)$

Space: $O(n)$

			


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;
  }
};




			


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;
  }
}




			


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