Table of contents
No headings in the article.
Let's continue to talk about the longest palindrome sub string question.The brute force way take has poor performance.
We can consider expanding a specific position from a string to find the longest palindrome sub-string.Look for each character and consider it as the middle of the palindrome string, then expand it from both directions.
For example:
We have a string like "ABABT". we can start from the first character "A", then we find the next one in the right direction is "B", is not match with "A".So we go to the second character "B".
The previous one is "A", and the next one is still "A".So it is matched, the longest sub string can be "ABA" so far.Then left direction is end, and the right direction we can go on.So we should look at the third character as before.
Here is the completed code:
package main
import "fmt"
func spread(s string, left int, right int) string {
if len(s) == 0 {
return ""
}
// If the string is palindrome string, expand it to both direction
for left >= 0 && right <= len(s)-1 && s[left] == s[right] {
left--
right++
}
return s[left+1 : right]
}
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
longestString := string(s[0])
for i := 0; i < len(s); i++ {
resOdd := spread(s, i, i)
resEven := spread(s, i, i+1)
if len(longestString) < len(resOdd) {
longestString = resOdd
}
if len(longestString) < len(resEven) {
longestString = resEven
}
}
return longestString
}
func isString()
func main() {
result := longestPalindrome("ABABCD")
fmt.Printf("result is %s", result)
}