3ms solution in C++ using simple approach


  • 0
    T

    This is almost similar approach to find the https://leetcode.com/problems/longest-palindromic-substring/

    This approach finds the possible substring that is palindrome starting from the end. Then, it will construct the string with required number or characters.

    class Solution {
        bool isPalindrome(string s){
            for (int i = 0, j = s.length() - 1;i < j;i++,j--)
                if (s[i]!=s[j]) return false;
            return true;
        }
    public:
        string shortestPalindrome(string s) {
            int len = s.length();
            if (isPalindrome(s)) return s;
            int end = len-1, left,right;
            while (end>=0){
                left = right = end;
                while (left>0 && s[left-1] == s[left]) left--;
                end = left-1;
                while (left>0 && right<len-1 && s[left-1] == s[right+1])
                    left--,right++;
                if (left == 0) break;
            }
            string str = "";
            if (right<len-1){
                str = s.substr(right+1);
                reverse(str.begin(),str.end());
            }
            return str+s;
        }
    };
    

Log in to reply
 

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