leetcode5：最长回文子串 #121

Activity

1. sisterAn

   added

   LeetCode

   腾讯

   on Oct 28, 2020
2. sisterAn commented on Oct 28, 2020

   

   sisterAn

   on Oct 28, 2020

   OwnerAuthor

   More actions

   解法：动态规划

   第 1 步：定义状态

   dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j] 。

   第 2 步：思考状态转移方程

   对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串

   dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

   第 3 步：初始状态：

   dp[i][i] = true // 单个字符是回文串
   if(s[i] === s[i+1]) dp[i][i+1] = true // 连续两个相同字符是回文串 

   代码实现：

   const longestPalindrome = (s) => {
     if (s.length < 2) return s
     // res: 最长回文子串
     let res = s[0], dp = []
     for (let i = 0; i < s.length; i++) {
       dp[i][i] = true
     }
     for (let j = 1; j < s.length; j++) {
       for (let i = 0; i < j; i++) {
         if (j - i === 1 && s[i] === s[j]) {
           dp[i][j] = true
         } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
           dp[i][j] = true
         }   
         // 获取当前最长回文子串
         if (dp[i][j] && j - i + 1 > res.length) {
           res = s.substring(i, j + 1)
         }
       }
     }
   
     return res
   }

   复杂度分析：

   • 时间复杂度：O(n²)
   • 空间复杂度：O(n²)

   leetcode
3. btea commented on Oct 29, 2020

   

   btea

   on Oct 29, 2020

   More actions

   dp初始化有问题吧，第一轮循环就会报错
4. syc666 commented on Jan 4, 2021

   

   syc666

   on Jan 4, 2021

   More actions

   中心扩散法

   function fn(str) {
       if(!str.length) return ''
       let res = str[0]
       const setRes = (j, k) => {
           if(str[j] !== str[k]) return
           while (str[j]&&str[j] === str[k]&&str[k]) {
               res = res.length >= j - k + 1 ? res : str.slice(k, j + 1)
               j++
               k--
           }
       }
       for (let i = 1, len = str.length; i < len; i++){
           setRes(i,i-1)
           setRes(i,i-2)
       }
       return res
   }
5. yokots commented on Jan 5, 2021

   

   yokots

   on Jan 5, 2021

   More actions

   动态规划法

   function longestPalindrome(s: string): string {
     // 字符串长度小于 2 返回
     if (s.length < 2) {
       return s;
     }
   
     // dp[i][j] 即字符串 s 下标从 i 到 j 是否为回文字符串。
     const dp: boolean[][] = [];
     // 默认子串为第一个字符, 即 dp[0][0]
     let res = s[0];
   
     for (let j = 1; j < s.length; j ++) {
       for (let i = 0; i <= j; i ++) {
         // 如果 dp[i] 未初始化，初始化为空数组。
         if (dp[i] === undefined) {
           dp[i] = [];
         }
   
         // 回文子串的长度
         const l = (j - i) + 1;
   
         // 首尾两个字符是否相等
         dp[i][j] = (s[i] === s[j]);
   
         // 如果长度小于等于 3，即 a, aa, aba, 首尾两个字符相等即该子串 i ~ j 是否是回文字符串
         // 大于 3 的情况下，判断首尾及上一轮比较情况，即 abcdcba, 即判断 a 和 a && b 和 b, 其中 b 和 b 的值又来自于 c 和 c, 依此类推
         if (l >= 4) {
           dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1];
         }
   
         // 如果是回文字符串且长度大于之前，重新赋值
         if (dp[i][j] && l > res.length) {
           res = s.substring(i, j + 1);
         }
       }
     }
   
     return res;
   };
   
   console.log(longestPalindrome("aacabdkacaa"));
6. XW666 commented on Jul 22, 2022

   

   XW666

   on Jul 22, 2022

   More actions

   >  function longestPalindrome(str) {
   
       let arr = []
       let fun = function (s) {
         for (let i = 0; i < s.length; i++) {
           let v = s[i]
           //查找 剩下字符中相同字符
           let index = s.substring(i + 1, s.length).indexOf(v)
           //存在
           if (index > -1) {
             arr.push(s.substring(i, index + 2))
           }
           //循环
           fun(s.substring(i + 1))
         }
       }
       fun(str)
     }