2
\$\begingroup\$

In this LeetCode problem, Longest Palindromic Substring, it is listed under Dynamic Programming for Google interview preparation. My understanding of dynamic programming is roughly "recursion + memoization + guessing." In the Python solution to this answer below it is not clear to me where the dynamic programming is if it exists at all. This is Approach 4 under solutions (translated from Java to Python). Approach 3 references dynamic programming but no solution is given.

Is there any dynamic programming going on here? Or is this just a solution to solve the problem in O(1) space, where the dynamic programming solution requires O(n^2) space?

This algorithm technically has a time complexity of O(n^2) right? Is this the best we could reasonably be expected to do in an interview?

class Solution:
    def longestPalindrome(self, s):
        res = ""
        for i in range(len(s)):
            # odd case, like "aba"
            tmp = self.helper(s, i, i)
            if len(tmp) > len(res):
                res = tmp
            # even case, like "abba"
            tmp = self.helper(s, i, i+1)
            if len(tmp) > len(res):
                res = tmp
        return res

    # get the longest palindrome, l, r are the middle indexes   
    # from inner to outer
    def helper(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]
\$\endgroup\$

closed as off-topic by vnp, esote, yuri, Ludisposed, pacmaninbw May 19 at 14:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Authorship of code: Since Code Review is a community where programmers improve their skills through peer review, we require that the code be posted by an author or maintainer of the code, that the code be embedded directly, and that the poster know why the code is written the way it is." – vnp, esote, yuri, Ludisposed, pacmaninbw
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Which website should this be included on? \$\endgroup\$ – Scott Skiles May 20 at 16:29