Python solution with detailed explanation


  • 0
    G

    Solution

    Dynamic Programming Approach: O(N^2) Time and O(N^2) Space

    • Base Case is length = 1 and length = 2.
    • Order of filling the matrix is diagonal wise. The way to do this is by varying the length from 3 to N in the outer loop.
    • DP results in TLE. There are optimizations to speed things up. For example, if there is no length 3 palindrome, we cannot have length 5 or 7 or 9 palindromes.
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            N = len(s)
            cache = [[False]*N for _ in range(N)]
            st, e = 0,0
            for i in range(N):
                cache[i][i] = True
                if i+1 < N:
                    cache[i][i+1] = (s[i] == s[i+1])
                    (st, e) = (i, i+1) if cache[i][i+1] else (st, e)
            # Incrementally build with increasing lengths from 3 to final        
            for length in range(3,len(s)+1):
                j = length-1
                for i in range(N):
                    if i+j < N:
                        cache[i][i+j] = cache[i+1][i+j-1] and (s[i] == s[i+j])
                        (st, e) = (i, i+j) if cache[i][i+j] else (st, e)
            return s[st:e+1]
    

    Expaning Centers: O(N^2) Time and O(1) Space

    • There are (2 * N - 1) centers. Even index centers are real and odd index centers are non real.
    • Expand around each of those centers. The method expand will expand s, starting from start and end and will do start-1 and end+1. This method just returns the total length expanded.
    • Now the arguments for expand (start and end) can be derived using i which ranges from 0 to 2 * N -1. Create an example and work out the formula.
    • In case of real center, total length of palindrome will be one more than what was returned from expand method. We can derive the indices which define the palindrome. Check the code.
    • THIS IS A TRICKY PIECE OF CODE - USE EXAMPLES TO DERIVE IT.
    class Solution(object):
        def expand(self, s, start, end):
            max_len = 0
            while start >= 0 and end <= len(s)-1:
                if s[start] == s[end]:
                    max_len, start, end = max_len+2, start-1, end+1
                else:
                    break
            return max_len
        
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            N = len(s)
            if N <= 1:
                return s
            max_len, max_s, max_e = 1, 0, 0
            for i in range((2*N)-1):
                if i % 2 == 0:
                    m_s, m_e = (i//2)-1, (i//2)+1
                    m = self.expand(s, m_s, m_e)
                    m=m+1
                    offset = ((m-1) // 2)-1
                else:
                    m_s, m_e = (i-1)//2, (i+1)//2
                    m = self.expand(s, m_s, m_e)
                    offset = (m // 2)-1
                if m > max_len:
                    max_len, max_s, max_e = m, m_s-offset, m_e+offset
            return s[max_s:max_e+1]
    

Log in to reply
 

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