longest palindrome recursive method when two characters at begin and end are equal why do we compare the count with rest of string?

user_3556956 0
Viewed 44

I am trying to understand the solution for longest palindrome in python with recursion method and dynamic programming (A- yet to understand why we call it dynamic programming)

I understand the base conditions

I understand when two characters are equal we move to the next characters inside the string i.e

c=_longestPalen(st, b+1, e-1, c+2)

B-BUT why on are we doing this

return bigger(c, bigger(_longestPalen(st, b+1,e,c), _longestPalen(st, b, e-1, c)))

Here is the entire code

def longestPalen(st):
    res=_longestPalen(st, 0,len(st)-1, 0)
    return res

def bigger(x, y):
    if x>y:
        return x
    else:
        return y

def _longestPalen(st, b,e,c):
    if e<b: return c
    if b==e: return c+1
    if st[b] == st[e]:
        c=_longestPalen(st, b+1, e-1, c+2)
        return bigger(c, bigger(_longestPalen(st, b+1,e,c), _longestPalen(st, b, e-1, c)))
    return bigger(_longestPalen(st, b+1, e, 0), _longestPalen(st, b, e-1, 0))
dynamic-programming recursion python
1 Answers

I've restructured the code slightly so it falls more in line with Python conventions:

def longest_palen(s):
    return _longest_palen(s, 0, len(s) - 1, 0)


def _longest_palen(s, b, e, c):
    if e < b:
        return c
    if b == e:
        return c + 1
    if s[b] == s[e]:
        return max(_longest_palen(s, b + 1, e - 1, c + 2),
                   _longest_palen(s, b + 1, e, c),
                   _longest_palen(s, b, e - 1, c))
    return max(
        _longest_palen(s, b + 1, e, 0),
        _longest_palen(s, b, e - 1, 0)
    )


if __name__ == '__main__':
    print(longest_palen("cyabbaxc"))  # abba   ("cyabbaxc"[2:6])
    print(longest_palen("cabbacxc"))  # cabbac ("cabbacxc"[:6])
    print(longest_palen("cxcabbac"))  # cabbac ("cxcabbac"[2:])

If the current first and last characters are the same there are four options:

  1. Both the current first and last character are in the Longest Palindrome.
    • Input: "abba"
    • Longest Palindrome: "abba" (4)
  2. Only the current first character is in the Longest Palindrome.
    • Input: "cabbacxc"
    • Longest Palindrome: "cabbac" (6)
    • Even though the first and last character are "c" only the first is in the longest palindrome, future recursive steps need to include testing "cabbacx" and "cabbac" to get the correct answer.
  3. Only the current last character is in the Longest Palindrome.
    • Input: "cxcabbac"
    • Longest Palindrome: "cabbac" (6)
    • Even though the first and last character are "c" only the last is in the longest palindrome, future recursive steps need to include testing "xcabbac" and "cabbac" to get the correct answer.
  4. Neither the current first nor last character are in the Longest Palindrome.
    • Input: "cyabbaxc"
    • Longest Palindrome: "abba" (4)
    • This case is taken care of in a future recursive step as the next step will be "yabbax" where we'll handle testing both "yabba" and "abbax".

The reason you are running

c = _longestPalen(str, b + 1, e - 1, c + 2)
return bigger(c, bigger(_longestPalen(str, b + 1, e, c), _longestPalen(str, b, e - 1, c)))

or

return max(_longest_palen(s, b + 1, e - 1, c + 2),
           _longest_palen(s, b + 1, e, c),
           _longest_palen(s, b, e - 1, c))

in the modified implementation, is to consider all of these cases.

The pseudo code for this line is something like:

bigger(both_first_last_included, bigger(only_first_included, only_last_included))

In the modified implementation, I use max which I find to be clearer in understanding what operation is taking place.

max(both_first_last_included, only_first_included, only_last_included)
user_154978880
Related