LeetCode – Q214 – Shortest Palindrome

This question, despite being solvable by a simple O(n^2) algorithm, almost took 2 hours of my life.

Simply because I was trying to get sub-palindromes, when instead, I should have checked for longest prefix of original string matching the suffix of its reverse.

E.g.           s = “abcda”

              reverse of s = rev = “adcba”

         longest suffix of rev matching s = “a”

              Answer = “adcbabcda”
           

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        int n = s.size();
        reverse(rev.begin(),rev.end());
        for(int i=n;i>0;i–)
        {
            if(!strncmp(s.substr(0,i).c_str(),rev.substr(n-i,i).c_str(),i))
                return rev.substr(0,n-i)+s;
        }
        return rev+s;
    }
};

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s