Algorithm
Problem Name: 214. Shortest Palindrome
You are given a string s. You can convert s to a palindrome (A palindrome is a string that reads the same forward and backward.) 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 * 104sconsists of lowercase English letters only.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
int i = 0, j = s.size();
while(r.substr(i, j) != s.substr(0, j)) i++, j--;
return r.substr(0, i) + s;
}
};
Input
s = "aacecaaa"
Output
"aaacecaaa"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const shortestPalindrome = function(s) {
let j = 0;
for (let i = s.length - 1; i >= 0; i--) {
if (s.charAt(i) === s.charAt(j)) { j += 1; }
}
if (j === s.length) { return s; }
let suffix = s.substring(j);
return suffix.split('').reverse().join('') + shortestPalindrome(s.substring(0, j)) + suffix;
};
Input
s = "aacecaaa"
Output
"aaacecaaa"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def shortestPalindrome(self, s, pre = ""):
for i in range(1, len(s) // 2 + 2):
if s[i - 1:].startswith(s[:i][::-1]): pre = s[2* i - 1:][::-1]
if s[i:].startswith(s[:i][::-1]): pre = s[2* i:][::-1]
return pre + s
Input
s = "abcd"
Output
"dcbabcd"