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

煮酒_zzh · · 762 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

原题链接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:

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

Input: "cbbd"
Output: "bb"

解题思路：基本就是无脑的”马拉车“算法（Manacher），其中的字符串处理部分用到了链接的现有函数

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.

花花酱的视频里面有DP方式求解的方法

有疑问加站长微信联系（非本文作者）