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