LeetCode.5 最長回文子串(longest-palindromic-substring)(J

Steven 發(fā)布于2019-08-23 16:47 / 2227人閱讀

摘要：一題目最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個有效答案。

一、題目

最長回文子串：

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

二、我的答案

思路

1.排除法，最優(yōu)解法肯定不是暴力遍歷
2.緊接著想到第三題中使用的兩個指針同步遍歷一個字符串的方法，嘗試了一下，發(fā)現(xiàn)跟暴力遍歷沒有區(qū)別
3.再看幾遍題，要找的是回文字符串，回文字符串的特點(diǎn)在于兩邊字符都相同，也就是說需要找的是兩邊字符都相同中間點(diǎn)(注意是中間點(diǎn)而不是中間字符，因?yàn)轭}干中例1的中間點(diǎn)是a，但是例2的中間點(diǎn)是bb)

代碼

v1.0(過于丑陋，可跳過直接看說明和v2.0)

   /**
    * @param {string} s
    * @return {string}
    */
    var longestPalindrome = function(s) {
     function expendString(index1, index2) {
       if(index1 > 0 && index2 + 1 < s.length &&s[index1 -1] === s[index2 + 1]){
         return expendString(index1 -1, index2 + 1)
       } else {
         return [index1, index2, index2 - index1]
       }
     }
     let longestArr = [0, 0, 0]
     let tempArr
     for(let i = 1; i< s.length; i++) {
       if(i + 1 < s.length&&s[i-1] === s[i+1]) {
         tempArr = expendString(i-1, i+1)
         tempArr[2] > longestArr[2] ? longestArr = tempArr : null
       }
       if(s[i -1] === s[i]) {
         tempArr = expendString(i - 1, i)
         tempArr[2] > longestArr[2] ? longestArr = tempArr : null
       }
     }
     return s.slice(longestArr[0], longestArr[1] + 1)
   };

講解

1. 函數(shù)expendString作用為以兩個傳參拓展字符串，判斷是否依然是回文字符串

2. 數(shù)組longestArr作用為防止當(dāng)前最長字串的兩個下標(biāo)和長度(我也不知道當(dāng)時自己為什么還要費(fèi)勁寫個數(shù)組)

3. for循環(huán)中判斷回文串的中點(diǎn)是一個("aba")還是兩個("abba"),然后分別調(diào)用上文定義的expendString函數(shù)進(jìn)行拓展

???????????通過，下一步要做的就是優(yōu)化成能看懂的版本

???????????v2.0

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s){
  function expendString(index1, index2) {
    if (index1 >= 0 && index2 < s.length && s[index1] === s[index2]) {
      expendString(index1 - 1, index2 + 1)
    } else {
      index2 - index1 > longestString.length ?
        longestString = s.slice(index1 + 1, index2) :
        null
    }
  }
  let longestString = s[0] || ""
  for (let i = 1; i < s.length; i++) {
    if (i + 1 < s.length) {
      expendString(i - 1, i + 1)
    }
    if (s[i - 1] === s[i]) {
      expendString(i - 1, i)
    }
  }
  return longestString
};