leetcode5

public class Solution {
        private int lo, maxLen;

        public String LongestPalindrome(String s)
        {
            int len = s.Length;
            if (len < 2)
                return s;

            for (int i = 0; i < len - 1; i++)
            {
                extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
                extendPalindrome(s, i, i + 1); //assume even length.
            }
            return s.Substring(lo, maxLen);
        }

        private void extendPalindrome(String s, int j, int k)
        {
            while (j >= 0 && k < s.Length && s[j] == s[k])
            {
                j--;
                k++;
            }
            if (maxLen < k - j - 1)
            {
                lo = j + 1;
                maxLen = k - j - 1;
            }
        }
}

https://leetcode.com/problems/longest-palindromic-substring/#/description

补充一个python的实现，使用动态规划解决：

 1 class Solution:
 2     def longestPalindrome(self, s: 'str') -> 'str':
 3         n = len(s)
 4         dp = [[False for _ in range(n)]for _ in range(n)]
 5         count = 0
 6         res = ''
 7         for i in range(n):
 8             dp[i][i] = True
 9             if count < 1:
10                 res = s[i]
11                 count = 1
12             
13         for i in range(n-1):
14             if s[i] == s[i+1]:
15                 dp[i][i+1] = True
16                 if count < 2:
17                     res = s[i:i+2]
18                     count = 2
19         
20         for k in range(3,n+1):
21             for i in range(n-k+1):
22                 j = i + k - 1
23                 if s[i] == s[j] and dp[i+1][j-1]:
24                     dp[i][j] = True
25                     if count < j + 1 - i:
26                         count = j + 1 -i
27                         res = s[i:j+1]
28         return res