Shortest Palindrome LeetCode Solution | Easy Approach

Shortest Palindrome You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of lowercase English letters only.

Shortest Palindrome Solutions

✅Time: O(n)
✅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

Watch Tutorial

Checkout more Solutions here