【LeetCode 0005】【动态规划】最长回文子串

5. Longest Palindromic Substring

Given a string s, return the longestpalindromicsubstring in s.

Example 1:

**Input:** s = "babad" **Output:** "bab" **Explanation:** "aba" is also a valid answer. 

Example 2:

**Input:** s = "cbbd" **Output:** "bb" 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

JavaScript Solution

/**  * @param {string} s  * @return {string}  */ var longestPalindrome = function(s) {     let [start,max] = [0,1]     // initial dp array     let dp = Array.from({length:s.length},(_,i)=>Array.from({length:i+1},()=>false))      // lower triangular matrix     /**     [         [ true ],         [ false, true ],         [ true, false, true ],         [ false, true, false, true ],         [ false, false, false, false, true ]     ]      */     let ans = ''     for( let i=0; i < s.length ; i++){       for(let j = i ; j >= 0 ; j-- ){         dp[i][j] = s[i]===s[j]&& (i-j<2 || dp[i-1][j+1])          if(dp[i][j] && ans.length < ( i - j + 1)){             ans = s.substring(j,i+1)         }       }     }     return ans };