Longest Palindrome Substring in a String

DP based solution

class Solution(object):
    def __init__(self):
        self.lookup  = {}
        
    def isPalindrome(self, s, dp, i, k):
        j = i + k - 1
        
        if s[i] == s[j] and dp[i + 1][j - 1]:
            return True
        
        return False
        
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        if size < 2:
            return s
        
        dp = [ [False]*size for c in range(size+1) ]
        
        i = j = 0
        longest = 0
        startIndex = endIndex = 0
        
        while i < size:
            dp[i][i] = True
            
            # Handle the case of two repeated chars ('bb')
            j = i + 1
            if j < size:
                if s[i] == s[j]:
                    dp[i][j] = True
                    
                    # Always update the index for result.
                    startIndex = i
                    endIndex = j
                    longest = 2
            i += 1
        
        # Start finding substrings longer the 2.            
        k = 3
        while k <= size:
            for i in range(0, size - k + 1):
                if self.isPalindrome(s, dp, i, k):
                    dp[i][i+k-1] = True
                    strLen = k
                    
                    if strLen > longest:
                        longest = strLen
                        startIndex = i
                        endIndex = i + k - 1
            k += 1
            
        return s[startIndex: endIndex + 1]

Resources

Written with StackEdit.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: