資訊專欄INFORMATION COLUMN
摘要：通過(guò)使用，我們將無(wú)論是奇數(shù)還是偶數(shù)的回文串，都變成了一個(gè)以為中心，為半徑兩個(gè)方向擴(kuò)展的問(wèn)題。并且就是回文串的長(zhǎng)度。
Given a string s, find the longest palindromic substring in s.
這題的意思是找出 最長(zhǎng)連續(xù)回文串。
思路來(lái)源于此
這里描述了一個(gè)叫Manacher’s Algorithm的算法。
算法首先將輸入字符串S， 轉(zhuǎn)換成一個(gè)特殊字符串T，轉(zhuǎn)換的原則就是將S的開(kāi)頭結(jié)尾以及每?jī)蓚€(gè)相鄰的字符之間加入一個(gè)特殊的字符，例如#
例如: S = “abaaba”, T = “#a#b#a#a#b#a#”.
為了找到最長(zhǎng)的回文字串，例如我們當(dāng)前考慮以Ti為回文串中間的元素，如果要找到最長(zhǎng)回文字串，我們要從當(dāng)前的Ti擴(kuò)展使得 Ti-d … Ti+d 組成最長(zhǎng)回文字串. 這里 d 其實(shí)和 以Ti為中心的回文串長(zhǎng)度是一樣的. 進(jìn)一步解釋就是說(shuō)，因?yàn)槲覀冞@里插入了 # 符號(hào)，對(duì)于一個(gè)長(zhǎng)度為偶數(shù)的回文串，他應(yīng)該是以#做為中心的，然后向兩邊擴(kuò)，對(duì)于長(zhǎng)度是奇數(shù)的回文串，它應(yīng)該是以一個(gè)普通字符作為中心的。通過(guò)使用#，我們將無(wú)論是奇數(shù)還是偶數(shù)的回文串，都變成了一個(gè)以Ti為中心，d為半徑兩個(gè)方向擴(kuò)展的問(wèn)題。并且d就是回文串的長(zhǎng)度。
代碼在控制臺(tái)調(diào)試如下：
首先對(duì)字符串進(jìn)行處理，~是規(guī)避數(shù)組以0開(kāi)頭，添加#號(hào)是為了規(guī)避字符串的單復(fù)數(shù)字節(jié)。
隨后找到回文字符串最中間的字節(jié)cs
再確定左右兩邊的字節(jié)個(gè)數(shù)
最后用數(shù)組方法Slice截取回文，用正則刪除#和~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/87290.html
摘要：題目描述給定一個(gè)字符串，找到中最長(zhǎng)的回文子串。你可以假設(shè)的最大長(zhǎng)度為。示例輸入輸出注意也是一個(gè)有效答案。示例輸入輸出思路分析暴力解法解決一個(gè)問(wèn)題如果沒(méi)有思路，就要想辦法從簡(jiǎn)單粗暴的解法開(kāi)始，然后想辦法優(yōu)化它。 題目描述 https://leetcode-cn.com/probl... 給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè)?s 的最大長(zhǎng)度為 1000。 示例 1： ...
摘要：題目解析題目是要找出最長(zhǎng)的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長(zhǎng)的子字符串即可了。但是這種解法遇到極端輸入狀況就會(huì)超時(shí)，指定的最長(zhǎng)長(zhǎng)度為，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為，那么極端狀況會(huì)超時(shí)。 題目 Given a string s, find the longest palindromic substring in s. You may ...
摘要：回文的意思就是反轉(zhuǎn)字符串后和原字符串相等。因?yàn)檫@種想法沒(méi)次都是兩邊同時(shí)擴(kuò)展。所以要分目標(biāo)字符串長(zhǎng)度為奇數(shù)目標(biāo)字符串為偶數(shù)兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...
摘要：題目即求最長(zhǎng)回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決，用及進(jìn)行兩層遍歷循環(huán)中套一層循環(huán)，用遍歷，求最長(zhǎng)回文序列字符串，同時(shí)用變量記錄最長(zhǎng)子序列這種寫(xiě)法很暴力，效率很低，一層循環(huán)，一層循環(huán)，回文序列對(duì)比一層，時(shí)間復(fù)雜度為辣 題目： Given a string s, find the longest palindromic substring in s. You ma...
摘要：這種解法中，外層循環(huán)遍歷的是子字符串的中心點(diǎn)，內(nèi)層循環(huán)則是從中心擴(kuò)散，一旦不是回文就不再計(jì)算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...
閱讀 3630·2019-08-30 15:55
閱讀 1423·2019-08-29 16:20
閱讀 3730·2019-08-29 12:42
閱讀 2721·2019-08-26 10:35
閱讀 1124·2019-08-26 10:23
閱讀 3475·2019-08-23 18:32
閱讀 990·2019-08-23 18:32
閱讀 2979·2019-08-23 14:55
