Accepted C++ solution, easy to understand.

  • 11

    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;

  • 0

    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:]:
            i = i + 1
        s = v[0:i] + s
        return s

  • 0

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

  • 0

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

  • 0

    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!

  • 0

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

  • 0

    @zalbert got it ,Thx!

  • 0

    good solution!

    why not just change the last 2 lines to this?

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

  • 0

Log in to reply

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