Question: Trying to understand a python algorithm solution to longest palidrome using dynamic programming, why do we need to check the condition if j-i ==1 or
Trying to understand a python algorithm solution to longest palidrome using dynamic programming, why do we need to check the condition if j-i ==1 or dp[i+1][j-1] is True: on line 11?
For example fucuf returns fucuf and pabad returns aba
def longestPalindrome(s): longest_palindrom = " " dp = [[0]*len(s) for _ in range(len(s))] for i in range(len(s)): dp[i][i] = True longest_palindrom = s[i] for i in range(len(s)-1,-1,-1): for j in range(i+1,len(s)): if s[i] == s[j]: if j-i ==1 or dp[i+1][j-1] is True: dp[i][j] = True if len(longest_palindrom) < len(s[i:j+1]): longest_palindrom = s[i:j+1] return longest_palindrom
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
