The approach using Longest Common Substring giving TLE in Python


  • 0
    D
    def lcs(S,T):
    m = len(S)
    n = len(T)
    counter = [[0]*(n+1) for x in range(m+1)]
    longest = 0
    lcs_set = set()
    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                c = counter[i][j] + 1
                counter[i+1][j+1] = c
                if c > longest and S.index(S[i-c+1:i+1]) == S.index(S[i-c+1:i+1][::-1]):
                    lcs_set = set()
                    longest = c
                    lcs_set.add(S[i-c+1:i+1])
                elif c == longest and S.index(S[i-c+1:i+1]) == S.index(S[i-c+1:i+1][::-1]):
                    lcs_set.add(S[i-c+1:i+1])
    
    return lcs_set
    
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            m = s
            n = s[::-1]
            l = lcs(m,n)
            return l.pop()

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.