最长回文子串 Golang leecode_5

先暴力

package main

import (
	"fmt"
)

func longestPalindrome(s string) string {
	bytes := []byte(s)
	var count int
	var res string = string(bytes[0])
	for i := 0; i < len(s); i++ {
		var temp string = string(bytes[i])
		for j := i + 1; j < len(s); j++ {
			temp = temp + string(bytes[j])
			if JudgePalindrome(temp) && count < len(temp) {
				res = temp
				count = len(temp)
			}
		}
	}
	return res
}

func JudgePalindrome(s string) bool {
	bytes := []byte(s)
	var res []byte
	for i := len(s) - 1; i > -1; i-- {
		res = append(res, bytes[i])
	}
	str := string(res)
	if str == s {
		return true
	} else if str != s {
		return false
	}
	return false
}

func main() {
	/*
		给你一个字符串 s，找到 s 中最长的回文子串。
		如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。*/
	s := "ccc"
	fmt.Println(longestPalindrome(s))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

发现虽然给的一些例子答案都对，但是提交的时候超时了，时间复杂度达到了O(n^3)，看看能不能优化。
我尝试着优化一下判断回文的函数，不用整个颠倒后来，只颠倒一半，如下：

func JudgePalindrome(s string) bool {
	length := len(s)
	if length%2 == 0 {
		slice1 := s[:length/2]
		slice2 := s[length/2:]
		var slice3 []byte
		for i := len(slice2) - 1; i > -1; i-- {
			slice3 = append(slice3, slice2[i])
		}
		if string(slice1) == string(slice3) {
			return true
		} else {
			return false
		}
	} else if length%2 == 1 {
		slice1 := s[:length/2]
		slice2 := s[length/2+1:]
		var slice3 []byte
		for i := len(slice2) - 1; i > -1; i-- {
			slice3 = append(slice3, slice2[i])
		}
		if string(slice1) == string(slice3) {
			return true
		} else {
			return false
		}
	}
	return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

还是超时，因为没有从数量级上降低时间复杂度，依然是O(n^3)，看来得从根本上优化。
看了一下 leecode 给的官方题解，采用了中心扩展算法将时间复杂度降到了 O(n^2)，主要的思想就是如果中心的子串是回文串，那么就尝试着向两边扩散，算法用 debug 跑一遍很好懂，代码如下：

func longestPalindrome(s string) string {
	if s == "" {
		return s
	}
	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		left1, right1 := ExpandPalindrome(s, i, i)
		left2, right2 := ExpandPalindrome(s, i, i+1)
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	return s[start : end+1]
}

func ExpandPalindrome(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
	}
	return left + 1, right - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

接下来是动态规划的代码题解，同样也是将时间复杂度降到了O(n^2)。官方题解有视频讲解

func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n)
    for i,_ := range dp {
        dp[i] = make([]bool, n)
    }
    ans := ""
    for l:=0; l<n; l++ { // l为本次循环遍历的子串长度
        for i:=0; i+l<n; i++ {
            j := i+l
            if l == 0 {
                dp[i][j] = true
            } else if l == 1 {
                dp[i][j] = (s[i] == s[j])
            } else {
                dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])
            }
            if dp[i][j] && l+1 > len(ans) {
                ans = s[i:j+1]
            }
        }
    }
    return ans
}

作者：Bonheur
链接：https://leetcode.cn/problems/longest-palindromic-substring/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29