My easily understandable but time consuming C++ solution


  • 44
    P

    The key idea is to first reverse the string, then check the max length from n to 0

    class Solution {
    public:
        string shortestPalindrome(string s) {
            string s2=s;
            reverse(s2.begin(),s2.end());
            int n=s.size(),l;
            for(l=n;l>=0;l--)
            {
                if(s.substr(0,l)==s2.substr(n-l))
                    break;
            }
            return s2.substr(0,n-l)+s;
        }
    };

  • 0
    C

    got TLE when translated to Java...


  • -1
    R

    is the time complexity O(n) ?


  • 1
    N

    No, n square.


Log in to reply
 

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