1
\$\begingroup\$

I want to find the longest palindromic substring using dynamic programming in Python3. The strings can be as large as this string.

I have seen other questions on this problem that successfully solve it but I am unable to improve my own code following their strategy.

This, approach 3 is the strategy that I want to implement. Even then, my code is not time-efficient.

My code is:

class Solution:

    def __init__(self):
        self.not_pal = {}
        self.pals = {}

    def check_pal(self, s, i, j):
        if len(s) == 0:
            return False
        if i == j:
            return True
        if i == j-1:
            if s[i] == s[j]:
                return True
            return False
        if s[i] == s[j]:
            return self.check_pal(s, i+1, j-1)
        return False

    def longestPalindrome(self, s):
        max_pal_str = ''
        length = len(s)
        for i in range(len(s)):
            if length-i <= len(max_pal_str):
                continue
            for j in range(len(s)-1, -1, -1):
                if self.not_pal.get(s[i: j+1]):
                    continue
                if self.pals.get(s[i: j+1]):
                    continue
                if len(s[i: j+1]) <= len(max_pal_str):
                    continue
                if self.check_pal(s, i, j):
                    self.pals[s[i:j+1]] = 1
                    if len(s[i: j+1]) > len(max_pal_str):
                        max_pal_str = s[i: j+1]
                else:
                    self.not_pal[s[i:j+1]] = 1
        return max_pal_str

I am unable to improve this code further. I expect it to be faster than brute force codes which check all the permutations and combinations without any memoization. It is failing with TLE on Leetcode.

\$\endgroup\$
6
  • 4
    \$\begingroup\$ Well, you succeeded in writing pretty unreadable code =) What's with all the the single-letter variable names and magic numbers? \$\endgroup\$
    – Mast
    Oct 30, 2019 at 17:21
  • \$\begingroup\$ @Mast I am sorry for writing bad code. i,j -> loop iterators s -> given string 1 is just any value in the dictionary(I should have used sets, right?) Is there any other friction for you to read the code? Apologies for presenting it in such a state. \$\endgroup\$ Oct 30, 2019 at 17:26
  • 1
    \$\begingroup\$ To counter-balance the unclear variable names, maybe you could add more context to your question :) This way, we could help you write clearer code. \$\endgroup\$
    – IEatBagels
    Oct 30, 2019 at 19:06
  • 2
    \$\begingroup\$ You say "The strings can be as large as this string", but which string do you mean? You also talk about "This, approach 3 is the strategy that I want to implement", but I have no idea what you mean by that. Please add a bit more detail, like the problem description and what your strategy to solve it actually is. \$\endgroup\$
    – Graipher
    Oct 31, 2019 at 15:25
  • \$\begingroup\$ Does the problem on Leetcode require that your code be in a class like this? \$\endgroup\$
    – AMC
    Nov 4, 2019 at 2:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.