5. 最长回文子串
2020-02-20 本文已影响0人
one_zheng
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
// 暴力法
func longestPalindrome(s string) string {
// 先在每一个字符串左右 拼接上'#'字符
ns := addRune(s, '#')
srune := []rune(ns)
var result string
for index, _ := range srune {
// 向左右两边扩展,判断字符串是否是回文字符
i, j := index, index
for {
if i < 0 || j > len(ns)-1 || srune[i] != srune[j] {
break
}
if j-i >= len(result) && i > -1 && j < len(ns) {
result = string(srune[i : j+1])
}
if srune[i] == srune[j] {
i--
j++
}
}
}
return removRune(result, '#')
}
func addRune(str string, char rune) string {
st := []rune(str)
nst := make([]rune, 0)
for _, s1 := range st {
nst = append(nst, char)
nst = append(nst, s1)
}
nst = append(nst, char)
return string(nst)
}
func removRune(str string, char rune) string {
st := []rune(str)
nst := make([]rune, 0)
for index, s1 := range st {
if index%2 == 0 {
continue
}
nst = append(nst, s1)
}
return string(nst)
}