Last updated on July 20th, 2024 at 04:10 am

Here, We see Shortest Palindrome LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

String

Companies

Google, Pocketgems

Level of Question

Hard

Shortest Palindrome LeetCode Solution

Problem Statement

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”

1. Shortest Palindrome Solution C++

class Solution {
public:
    string shortestPalindrome(string s) {
        string t = process(s);
        int n = t.length(), center = 0, right = 0;
        int* palin = new int[n];
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * center - i;
            palin[i] = (right > i) ? min(palin[i_mirror], right - i) : 0;
            while (t[i + palin[i] + 1] == t[i - palin[i] - 1])
                palin[i]++;
            if (i + palin[i] > right) {
                center = i;
                right = i + palin[i];
            }
        }
        int pos;
        for (int i = n - 2; i; i--) {
            if (i - palin[i] == 1) {
                pos = palin[i];
                break;
            }
        }
        string tail = s.substr(pos); 
        reverse(tail.begin(), tail.end());
        return tail + s;
    }
private:
    string process(string& s) {
        int n = s.length();
        string t(2 * n + 3, '#');
        t[0] = '$'; t[2 * n + 2] = '%';
        for (int i = 0; i < n; i++)
            t[2 * (i + 1)] = s[i];
        return t;
    }
};

2. Shortest Palindrome Solution Java

class Solution {
    public String shortestPalindrome(String s) {
            int j = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(j)) { j += 1; }
        }
        if (j == s.length()) { return s; }
        String suffix = s.substring(j);
        return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;
    }
}

3. Shortest Palindrome Solution JavaScript

var shortestPalindrome = function(s) {
	var prefix = "";
	var pos, head, tail;
	for (pos = head = tail = parseInt(s.length / 2); pos > 0; head = tail = --pos) {
		while (head !== 0 && s[head - 1] === s[head]) {
			head--;
			pos--;
		}
		while (tail != s.length - 1 && s[tail + 1] === s[tail]) {
			tail++;
		}
		var isSame = true;
		while (head >= 0) {
			if (s[head] !== s[tail]) {
				isSame = false;
				break;
			}
			head--;
			tail++;
		}
		if (isSame) {
			break;
		}
	}
	for (var k = s.length - 1; k >= tail && k !== 0; k--) {
		prefix += s[k];
	}
	return prefix + s;
};

4. Shortest Palindrome Solution Python

class Solution(object):
    def shortestPalindrome(self, s):
        r = s[::-1]
        for i in range(len(s) + 1):
            if s.startswith(r[i:]):
                return r[:i] + s