214 Shortest Palindrome
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given
"aacecaaa", return"aaacecaaa".Given
"abcd", return"dcbabcd".Brute Force idea: check for matching substrings
Ex1:
abcd
dcba
abc
cba
ab
ba
a
a
Ex2:
adcbabcd
aacecaaa
aaacecaa
aacecaa
aacecaa
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
const size_t size = s.length();
int i = 0;
for (i; i < size; i++) {
if (s.substr(0, size - i) == r.substr(i))
break;
}
return r.substr(0, i) + s;
}
int main()
{
cout << shortestPalindrome("abcd") << endl;
cout << shortestPalindrome("aacecaaa") << endl;
}
Last modified 4yr ago