# Accepted C++ solution, easy to understand.

• The general idea is very simple: reverse s at first and compare substr of s with its reversed version.

``````string shortestPalindrome(string s)
{
int n = s.size();
if(n == 0) return s;

int i = n;
string v = s;
reverse(v.begin(), v.end());  //Reverse s.

for(; i >= 1; --i)
{
if(s.substr(0, i) == v.substr(n - i)) break;    //palindrome?
}
for(; i < s.size(); i += 2) s = s[i] + s;   //Construct
return s;
}``````

• This is the best answer I have ever seem. The following is its python equivalence.

``````class Solution(object):
def shortestPalindrome(self, s):
v = s[::-1]
i = 0
l = len(s)
while i < l:
if s[0:l-i] == v[i:]:
break
i = i + 1
s = v[0:i] + s
return s``````

• I have the similar idea as yours. It's cool and elegant, but frankly speaking, string compare is O(n) time complexity, although we are simply using "==".

• Why would it pass without getting TLE? I suppose the time complexity is O(n*n), isn't it?

• Hi，your answer is cool ,but I can't fully understand the "i+=2" in the second for circulation, why not "i+=1"? can u explain it?thanks!

• @Thinkle Because s = s[i] + s, which means the length of s is increased by 1, thus, we should increase i by 2 to skip the newly add character.

• @zalbert got it ,Thx!

• good solution!

why not just change the last 2 lines to this?

``````return v.substr(0, n - i) + s;
``````

• great!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.