中等- LeetCode 5.最长回文子串

题目

来源：最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

解题思路及代码

1.思路

采用中心扩散法：在字符串的任意位置时，向两边扩散，遇到不是回文的时候就结束，在这个过程中要保证不越界。首先往左寻找与当前位置相同的字符，直到遇到不相等为止 。然后往右寻找与当前位置相同的字符，直到遇到不相等为止。最后左右双向扩散，直到左和右不相等。

2.代码

var longestPalindrome = function(s) {
     if (s == null || s.length == 0) {
         return "";
     }
     var len = s.length;
     var left = 0;
     var right = 0;
     var maxLen = 0;
     var maxStart = 0;
     var newLen = 1;
     for (var i = 0; i < len; i++) {
         left = i - 1;
         right = i + 1;
         while (left >= 0 && s.charAt(left) == s.charAt(i))  {
             newLen++;
             left--;
         }
         while (right < len && s.charAt(right) == s.charAt(i)) {
             newLen++;
             right++;
         }
         while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
             newLen += 2;
             left--;
             right++;
         }
         if (newLen > maxLen) {
             maxLen = newLen;
             maxStart = left;
         }
         newLen = 1;
     }
     return s.substr(maxStart+1, maxLen);

 };

也可采用动态规划
dp[i][j]=1表示字符串从i到j这段为回文。若确定[i-1][j+1]为回文串，只需要确定dp[i][j]=1，且字符串在(i-1)和(j+1)两个位置字符相同，动态规划关键是找到初始状态和状态转移方程。
初始状态，i=j, 此时 dp[i][j]=1。
状态转移方程，dp[l][r]=1 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=1。

代码中 j - i < 2 表示两个元素相邻时。