Accepted 4ms c++ solution, different with KMP-based solution and easy understand.


  • 17

    For this problem, KMP-based solution is a very typical and classic O(n) solution. Here is a different solution, it's also O(n), and I think it is more easy to understand.

    In order to slove this problem, the key is to get the length of the longest palindromic prefix substring. if the length of s is len, and the length of the longest palindromic prefix substring is longest, the remaining substring will be s.substr(longest, len - longest), than we should reverse the remaining substring and adding it in front of s.

    For example, if s is "abacbbcda", so the longest palindromic prefix substring is "aba"(not "cbbc" because it's not prefix string), and the remaining substring is "cbbcda", we reverse the remaining substring and get "adcbbc", so the result is "adcbbc" + "abacbbcda".

    The follow is my c++ solution, only 4ms. Please note that the condition in for loop is begin <= len / 2 instead of begin < len, because if begin > len / 2, the substring can not be prefix string, so there is no need to continue.

    Update: I made wrong analysis, the complexity is O(N^2) but not O(N). Thanks very much for Sammax's reminder.

    class Solution {
    public:
        std::string shortestPalindrome(std::string s) {
    		int len = s.length();
    		if (len < 2)
    			return s;
    		// calculate the length of the longest palindromic prefix substring.
    		int longest = 1, start, end;
    		for (int begin = 0; begin <= len / 2;) {
    			start = end = begin;
    			while (end < len - 1 && s[end + 1] == s[end])
    				++end;
    			begin = end + 1;
    			while (end < len - 1 && start > 0 && s[end + 1] == s[start - 1]) {
    				++end;
    				--start;
    			}
    			// start == 0 means the palindromic substring is also prefix string.
    			if (start == 0 && longest < end - start + 1)
    				longest = end - start + 1;
    		}
    		// reverse the remaining substring and adding it in front of s.
    		std::string remaining = s.substr(longest, len - longest);
    		std::reverse(remaining.begin(), remaining.end());
    		return remaining + s;
        }
    };
    

  • 12
    S

    Your solution is interesting, but unfortunately it's not O(n).
    It runs in O(n ^ 2) on a test like "abababababababababababababababababababababab"

    Tests are pretty weak for some reason and a lot of O(n ^ 2) solutions pass them, even tho the problem difficulty is supposed to be hard.


  • 0
    S

    Unfortunately, your code may contain errors, which are not detected by the test cases.
    In fact, your solution will still TLE for some test cases.

    What does the following code snippet do? I think they are merely inserted to cheat the judge program:
    ...
    while (end < len - 1 && s[end + 1] == s[end])
    ++end;
    begin = end + 1;


  • 0

    Based on your comment, I think you haven't understand the code, but why you think it may contain errors? It's a bit contradictory, can you give me some error examples?


  • 0
    S

    Clearly, your code contains the logic by skipping long repeated characters, and your code will TLE on test cases like this one "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab"


  • 0

    I know, this is the worst example, Sammax has been remind me. The complexity is O(N^2), but it's right. And

    while (end < len - 1 && s[end + 1] == s[end]) ++end;
    begin = end + 1;
    

    is useful in the solution.


  • 0
    Q

    Based on the same idea as yours. But getting TLE! PLease help!

    class Solution {
    public:
    
    string reverse(string s)
    {
        return string(s.rbegin(), s.rend());
    }
    
    bool isPal(string s)
    {
        if (s == reverse(s))
            return true;
        else
            return false;
    }
    string shortestPalindrome(string s) 
    {
        int n = s.length(), i;
        
        if (len < 2)
            return s;
        
        if(isPal(s))
            return s;
        
        for(i=n-1; i>2; i--)
        {
            if(isPal(s.substr(0,i)))
                break;
        }
        s=reverse(s.substr(i,n-i-1)) + s;
        return s;
    }
    };
    

    I am getting error Time Limit exceeded!
    Last executed input:
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa....."


  • 0

    The solution is O(n^2), now it will get error Time Limit exceeded because more test cases have been added.


  • 0
    Q

    Okay! Thanks much :)


  • 0
    T

    It still can AC at this time. Even though O(n^2), the best part is using i = end + 1 to advance index instead of checking each letter, thus, it can accelerate on cases like aaaaaa..........


Log in to reply
 

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