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

Steven 發布于2019-08-23 16:47 / 2235人閱讀

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

一、題目

最長回文子串：

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

示例 1：

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

示例 2：

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

二、我的答案

思路

1.排除法，最優解法肯定不是暴力遍歷
2.緊接著想到第三題中使用的兩個指針同步遍歷一個字符串的方法，嘗試了一下，發現跟暴力遍歷沒有區別
3.再看幾遍題，要找的是回文字符串，回文字符串的特點在于兩邊字符都相同，也就是說需要找的是兩邊字符都相同中間點(注意是中間點而不是中間字符，因為題干中例1的中間點是a，但是例2的中間點是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. 函數expendString作用為以兩個傳參拓展字符串，判斷是否依然是回文字符串

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

3. for循環中判斷回文串的中點是一個("aba")還是兩個("abba"),然后分別調用上文定義的expendString函數進行拓展

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

???????????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
};

GPU云服務器云服務器 java最長相同子串最長公共子串 java回文程序 java公共子串

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/103288.html

LeetCode代碼分析——5. longest-palindromic-substring（動態規

摘要：題目描述給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。示例輸入輸出思路分析暴力解法解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優化它。題目描述 https://leetcode-cn.com/probl... 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設?s 的最大長度為 1000。示例 1： ...

neuSnail 2019-08-19 10:35 評論0 收藏0
[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長回文子串

摘要：難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數字母的回文和偶數字母的回文中心是不一樣的奇數字母比如的中心在中間字母上偶數字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 評論0 收藏0
最長回文子串——Manacher 算法

摘要：問題定義最長回文子串問題給定一個字符串，求它的最長回文子串長度。可以采用動態規劃，列舉回文串的起點或者終點來解最長回文串問題，無需討論串長度的奇偶性。 0. 問題定義最長回文子串問題：給定一個字符串，求它的最長回文子串長度。如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評論0 收藏0
獲取最長回文子串

摘要：以下是最長回文子串的相關代碼，相關邏輯已在注釋中注明我們原有的字符串可能存在兩種回文子串，一種是具有基數個元素例如一種是具有偶數個元素例如這樣的話分情況判斷比較復雜所以我們對原字符串進行擴充在相鄰元素中插入特殊值插入后的原基數回文子串變成了以下是最長回文子串的Manacher‘s Algorithm相關代碼，相關邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評論0 收藏0