C++ O(N^2) 4ms cheat, could inspire better algorithm?


  • 1
    O

    Hey,

    As many people just got stuck on 'aaaaaaa...aacdaaaaaa.aaaa' case, so decided to abuse property that every letter in palindrome must either appear twice or be in middle. Hence first single letter must either be in middle of palindrome, or be outside palindrome. Will look into other suggested methods.

    class Solution {
        private:
        bool is_palindrome(string s, int start, int end){
            int i=start, j=end;
            while(i<j && s[i]==s[j]){i++;j--;}
            return i>=j;
        }
    public:
        string shortestPalindrome(string s) {
            int lett_counts[26] = {0};
            int end = s.size()-1;
            for(int i=0;i<=end;i++) lett_counts[s[i]-'a']++;
            int first_single_letter = 0;
            while(first_single_letter<=end && lett_counts[s[first_single_letter]-'a']!=1) first_single_letter++;
            if (first_single_letter<=end/2 && is_palindrome(s, 0, first_single_letter*2)) end = first_single_letter*2;
            else{
                end = first_single_letter;
                while(!is_palindrome(s, 0, end)) end--;
            }
            string out;
            for(int j=s.size()-1;j>end;j--) out+=s[j];
            out+=s;
            return out;
        }
    };

  • 0
    D

    maybe should add a test case with all letters appeared even times


Log in to reply
 

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