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".

 

1 public class Solution { 2     public string ShortestPalindrome(string s) { 3         int i = 0, end = s.Length - 1, j = end; 4          5         while (i < j) 6         { 7             if (s[i] == s[j]) 8             { 9                 i++;10                 j--;11             }12             else13             {14                 i = 0;15                 end--;16                 j = end;17             }18         }19         20         var sb = new StringBuilder();21         22         for (int k = s.Length - 1; k > end; k--)23         {24             sb.Append(s[k]);25         }26         27         for (int k = 0; k < s.Length; k++)28         {29             sb.Append(s[k]);30         }31         32         return sb.ToString();33     }34 }