My python solution with o(n^2), but Time Limit Exceeded? Coundl


  • 0
    B

    My idea is very simple. the longest palindromic substring could convert to longgest common substring. we just need to reverse the origin string as rs. Then the longgest common substring will be the longest palindromic substring. Here is my
    solution. But time limit is exceeded. Who could help me?

     rs = list(s)
            rs.reverse()
            rs = "".join(rs)
            ls = len(s)
            pind = [0]*ls
            mp = 0
            mas = []
            ind = 0
            while ind < ls:
                cind = [0]*ls
                j = 0
                while j < ls:
                    if rs[ind] == s[j]:
                        if j == 0:
                            cind[j] = 1
                        else:
                            cind[j] = pind[j-1] + 1
                    if cind[j] > mp:
                        mp = cind[j]
                        mas = [ind, j]
                    j += 1
                ind += 1
                pind = cind
            return s[mas[1]-mp+1:mas[1]+1]
    

  • 0
    M

    Your idea may not work in all cases, see this link: Common Mistake


  • 0
    B

    @mrsan22 thanks! This solution also slower than Two pointer.


Log in to reply
 

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