Greedily return longest first; easy to understand; C++


  • 0
    E

    I believe this algorithm is faster than dynamic programming and faster than algorithms that expand until the maximum length is found, because this algorithm starts at the longest possible, and greedily returns the longest first.

    class Solution {
    public:
        // Optimization for long palindromes:
        // Contract begin and end outward from outside.
        // Greedily return first found, which is the longest.  O(n^2)
        // Worst case short-circuits third interior loop and consumes constant memory.
        // String under 1 is a trivial case and returns original string.
        // If no palindrome found, returns first character.
        // Palindrome of length 3 or less can short circuit,
        // since the interior of three letters or less is certainly a palindrome too.
        //
        // Compare this to dynamic program:
        // Start and end, check if palindrome  O(n^2) time and O(n^2) memory.
        // Outward in, check if values are equal.
        // Cache interior palindromes in tableau of begin and end indexes.
        // Store indexes of longest palindrome.
        // Return substring between these indexes.
        string longestPalindrome(string s) {
            size_t size = s.size();
            if (size <= 1)
            {
                return s;
            }
            for (size_t length = size; 2 <= length; --length)
            {
                for (size_t begin = 0, beginMax = size - length; begin <= beginMax; ++begin)
                {
                    size_t end = begin + length - 1;
                    for (size_t inBegin = begin, inEnd = end; s[inBegin] == s[inEnd]; ++inBegin, --inEnd)
                    {
                        if (inEnd <= inBegin + 2)
                        {
                            return s.substr(begin, end - begin + 1);
                        }
                    }
                }
            }
            return s.substr(0, 1);
        }
    };
    

Log in to reply
 

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