最長(zhǎng)回文子串

jemygraw 發(fā)布于2019-08-23 14:44 / 3119人閱讀

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

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

示例 1：

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

示例 2：

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

用的Manacher算法

var longestPalindrome = function(s) {
    if (s.length == 0) return ""
    var str="$"
    var j = 1,mx = 0,id = 0, len = [];
    var max=0, index;
    for(var i = 0, l = s.length; i < l; i++) {
        str += "#";
        str += s[i]
    }
    str += "#"
    for (var i = 1, l = str.length; i < l; i++) {
        if(i < mx) {
            len[i] = Math.min(len[2*id - i], mx - i)
        } else {
            len[i] = 1;
        }
        while(str[len[i] + i] == str[i - len[i]]) {
            len[i]++;
        }
        if (len[i] + i > mx) {
            id = i;
            mx = len[i] + i;
            if (len[i] > max) {
                max = len[i];
                index = i;
            }
        }
    }
    return s.substr((index - max) / 2, max - 1)
};

GPU云服務(wù)器云服務(wù)器最長(zhǎng)公共子串 java最長(zhǎng)相同子串最長(zhǎng)遞增短信最長(zhǎng)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/101061.html

相關(guān)文章

獲取最長(zhǎng)回文子串

摘要：以下是最長(zhǎng)回文子串的相關(guān)代碼，相關(guān)邏輯已在注釋中注明我們?cè)械淖址赡艽嬖趦煞N回文子串，一種是具有基數(shù)個(gè)元素例如一種是具有偶數(shù)個(gè)元素例如這樣的話分情況判斷比較復(fù)雜所以我們對(duì)原字符串進(jìn)行擴(kuò)充在相鄰元素中插入特殊值插入后的原基數(shù)回文子串變成了以下是最長(zhǎng)回文子串的Manacher‘s Algorithm相關(guān)代碼，相關(guān)邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評(píng)論0 收藏0
最長(zhǎng)回文子串——Manacher 算法

摘要：?jiǎn)栴}定義最長(zhǎng)回文子串問(wèn)題給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。可以采用動(dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來(lái)解最長(zhǎng)回文串問(wèn)題，無(wú)需討論串長(zhǎng)度的奇偶性。 0. 問(wèn)題定義最長(zhǎng)回文子串問(wèn)題：給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評(píng)論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長(zhǎng)回文子串

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

NotFound 2019-08-14 17:12 評(píng)論0 收藏0
LeetCode.5 最長(zhǎng)回文子串(longest-palindromic-substring)(J

摘要：一題目最長(zhǎng)回文子串給定一個(gè)字符串，找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。一、題目最長(zhǎng)回文子串：給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。示例 1：輸入: babad輸出: bab注意: aba 也是一個(gè)有效答案。示例 2：輸入: cbbd輸出: bb 二、我的答案思路 1.排...

Steven 2019-08-23 16:47 評(píng)論0 收藏0
LeetCode5.最長(zhǎng)回文子串 JavaScript

摘要：最長(zhǎng)回文子串給定一個(gè)字符串，找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。 LeetCode5.最長(zhǎng)回文子串 JavaScript 給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。示例 1：輸入: babad 輸出: bab 注意: aba 也是一個(gè)有效答案。示例 2：輸入: cbbd輸出: bb /*...

philadelphia 2019-08-23 14:45 評(píng)論0 收藏0