5. Longest Palindromic Substring

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路

和LCS道理一样，对比s和它的reverse，用DP填表，再通过backtrace找到string

具体做法

1. 建一个reverse的string、一个存DP的2D list
2. 填表时，如果两个string的char一样，填 “左上方的值+1”； 否则填“左边和上边的最大值”
3. Backtrace时，从右下角开始，如果跟左边数字一样，往左移；跟上面一样，往上移；只有当不一样的时候，加到ans里并且往左上移

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        rev = s[::-1]
        list = [[0 for i in range(length+1)] for j in range(length+1)]
        for a in range (length):
            for b in range (length):
                if(s[a] == rev[b]):
                    list[a+1][b+1] = list[a][b] + 1
                else:
                    list[a+1][b+1] = max(list[a][b+1],list[a+1][b])
        aa = bb = length
        ret = ""
        while (aa > 0 or bb > 0):
            if (list[aa][bb] == list[aa-1][bb]):
                aa -= 1
            elif (list[aa][bb] == list[aa][bb-1]):
                bb -= 1
            else:
                ret += s[aa-1]
                aa -= 1
                bb -= 1
        return ret