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]