Leetcode -- Longest Palindromic Substring

Solution 03/30/2014 O(n3)-- Time Limit Exceeded Last executed input: "zudfweormatjycujjirzjpyrmaxurectxrtqedmmgergwdvjmjtstdhcihacqnothgttgqfywcpgnuvwglvfiuxteopoyizgehkwuvvkqxbnufkcbodlhdmbqyghkojrgokpwdhtdrwmvdegwycecrgjvuexlguayzcammupgeskrvpthrmwqaqsdcgycdupykppiyhwzwcplivjnnvwhqkkxildtyjltklcokcrgqnnwzzeuqioyahqpuskkpbxhvzvqyhlegmoviogzwuiqahiouhnecjwysmtarjjdjqdrkljawzasriouuiqkcwwqsxifbndjmyprdozhwaoibpqrthpcjphgsfbeqrqqoqiqqdicvybzxhklehzzapbvcyleljawowluqgxxwlrymzojshlwkmzwpixgfjljkmwdtjeabgyrpbqyyykmoaqdambpkyyvukalbrzoyoufjqeftniddsfqnilxlplselqatdgjziphvrbokofvuerpsvqmzakbyzxtxvyanvjpfyvyiivqusfrsufjanmfibgrkwtiuoykiavpbqeyfsuteuxxjiyxvlvgmehycdvxdorpepmsinvmyzeqeiikajopqedyopirmhymozernxzaueljjrhcsofwyddkpnvcvzixdjknikyhzmstvbducjcoyoeoaqruuewclzqqqxzpgykrkygxnmlsrjudoaejxkipkgmcoqtxhelvsizgdwdyjwuumazxfstoaxeqqxoqezakdqjwpkrbldpcbbxexquqrznavcrprnydufsidakvrpuzgfisdxreldbqfizngtrilnbqboxwmwienlkmmiuifrvytukcqcpeqdwwucymgvyrektsnfijdcdoawbcwkkjkqwzffnuqituihjaklvthulmcjrhqcyzvekzqlxgddjoir"

class Solution {

public:

    string longestPalindrome(string s) {

        string palin;

        size_t n = s.length();

       

        for(size_t i = 0; i < n && n - i > palin.length(); i++) {

            for(size_t j = i; j < n ; j++) {

                std::string sub(s.substr(i,j - 1 + 1));

                if(isPalindrome(sub)) {

                    palin = palin.length() > sub.length() ? palin : sub;

                }

            }

           

        }

        return palin;

    }

   

    bool isPalindrome(string s) {

        size_t n = s.length();

       

        for(size_t i = 0; i < n / 2; i++) {

            if(s[i] != s[n - i - 1]) {

                return false;

            }

        }

        return true;

    }

};

Solution 03/30/2014 O(n2)

class Solution {

public:

    string longestPalindrome(string s) {

        size_t n = s.length();

        if(s == "") {

            return "";

        }

       

        string longest(s.substr(0, 1));

        for(size_t i = 0; i < n - 1; ++i) {

            string pOdd = expandFromCenter(s, i, i);

            longest = longest.length() > pOdd.length() ? longest : pOdd;

           

            string pEven = expandFromCenter(s, i, i+1);

            longest = longest.length() > pEven.length() ? longest : pEven;

        }

        return longest;

       

    }

   

    string expandFromCenter(string s, size_t c1, size_t c2) {

        size_t n = s.length();

        size_t l = c1, r = c2;

   

        while(l >=0 && r < n && s[l] == s[r]) {

            l--;

            r++;

        }

        return s.substr(l + 1, r - l - 1);

    }

};