Accepted C++ solution, easy to understand.


  • 11
    B

    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
    X

    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

  • 0
    Z

    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
    M

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


  • 0
    T

    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
    Z

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

    @zalbert got it ,Thx!


  • 0
    Y

    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.