Shortest Palindrome
Desicription 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.
Example 1:
1 2 Input: "aacecaaa" Output: "aaacecaaa"
Example 2:
1 2 Input: "abcd" Output: "dcbabcd"
Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : string shortestPalindrome (string s) { if (s.size() < 2 ) { return s; } int max_length = 1 ; for (int i = 0 ; i <= s.size() / 2 ; ) { int left = i; int right = i; while (s[i] == s[right + 1 ]) { right++; } i = right; while (left - 1 >= 0 && right + 1 <= s.size() - 1 && s[left - 1 ] == s[right + 1 ]) { left--; right++; } if (left == 0 ) { max_length = max(max_length, right - left + 1 ); } i++; } string tail_string = s.substr(static_cast <unsigned int >(max_length)); reverse(tail_string.begin(), tail_string.end()); return tail_string + s; } };