Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
題目和第三題類似祖今,求給定字符串中最大回文字符串贺归。
第一次提交出現(xiàn)TLE(超時)冕广,后將第二層循環(huán)初始條件j:=i+1改為j:=i+len(output)甸赃,既小于已知最長結(jié)果的字符串都不再檢測,通過衣赶。
解法如下:
func longestPalindrome(s string) string {
var output []byte
bs := []byte(s)
if len(bs) > 0 {
output = bs[0:1]
}
for i := 0; i < len(bs); i++ {
for j := i + len(output); j < len(bs); j++ {
flag := 0
for k := 0; k < (j-i+1)/2; k++ {
if bs[k+i] != bs[j-k] {
flag = 1
break
}
}
if flag == 0 && j-i+1 > len(output) {
output = bs[i : j+1]
}
}
}
return string(output)
}