leetcode刷题笔记(Golang)--5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

``````func longestPalindrome(s string) string {
if s == "" {
return ""
}
id, mx := 0, 0
sTrans := initManacherStr(s)
res := 0
var path []int = make([]int, len(sTrans))
for i, _ := range sTrans {
if i < mx {
lg := path[2*id-i]
if mx-i < lg {
lg = mx - i
}
path[i] = lg
} else {
path[i] = 1
}

for i-path[i] >= 0 && i+path[i] < len(sTrans) && sTrans[i-path[i]] == sTrans[i+path[i]] {
path[i] += 1
}

if path[i] > path[res] {
res = i
}

if i+path[i] > mx {
mx = i + path[i]
id = i
}
}
return strings.Replace(sTrans[(res-path[res]+1):(res+path[res])], "#", "", -1)
}

func initManacherStr(s string) string {
ans := make([]rune, 0)
ans = append(ans, '#')
for i := 0; i < len(s); i++ {
ans = append(ans, rune(s[i]), '#')
}
return string(ans)
}
``````

Runtime: 0 ms, faster than 100.00% of Go online submissions for Longest Palindromic Substring.

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

``````func longestPalindrome(s string) string {
if s == "" {
return ""
}
id, mx := 0, 0
sTrans := initManacherStr(s)
res := 0
var path []int = make([]int, len(sTrans))
for i, _ := range sTrans {
if i < mx {
lg := path[2*id-i]
if mx-i < lg {
lg = mx - i
}
path[i] = lg
} else {
path[i] = 1
}

for i-path[i] >= 0 && i+path[i] < len(sTrans) && sTrans[i-path[i]] == sTrans[i+path[i]] {
path[i] += 1
}

if path[i] > path[res] {
res = i
}

if i+path[i] > mx {
mx = i + path[i]
id = i
}
}
return strings.Replace(sTrans[(res-path[res]+1):(res+path[res])], "#", "", -1)
}

func initManacherStr(s string) string {
ans := make([]rune, 0)
ans = append(ans, '#')
for i := 0; i < len(s); i++ {
ans = append(ans, rune(s[i]), '#')
}
return string(ans)
}
``````

Runtime: 0 ms, faster than 100.00% of Go online submissions for Longest Palindromic Substring.