Sharing my 4ms C++ solution


  • 6
    T
    class Solution {
    public:
        string shortestPalindrome(string s) {
            int n = s.length();
            int leftMost=0;
            int rightMost=0;
            int i=0, start, end;
            while(i<n)
            {
                start = i;
                while(s[i]==s[start])
                {
                    i++;
                }
                end = i-1;
                while(start-1>=0 && end+1<n && s[start-1]==s[end+1])
                {
                    start--;
                    end++;
                }
                if(start==0 && (end-start) > (rightMost-leftMost))
                {
                    leftMost = 0;
                    rightMost = end;
                }
            }
            
            string result;
            if(rightMost<n-1)
            {
                result = s.substr(rightMost+1, n-rightMost);
                reverse(result.begin(), result.end());
            }
            result = result + s;
            
            return result;
        }
    };

Log in to reply
 

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