## 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 * 104`
• `s` consists 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;
}
};
``````
Copy The Code &

Input

cmd
s = "aacecaaa"

Output

cmd
"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;
};
``````
Copy The Code &

Input

cmd
s = "aacecaaa"

Output

cmd
"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
``````
Copy The Code &

Input

cmd
s = "abcd"

Output

cmd
"dcbabcd"