LeetCode-Go/5.go at master · HugoWen/LeetCode-Go · GitHub

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
package main

func longestPalindrome(s string) string {
    l := len(s)
    if l < 2 {
        return s
    }

    dp := make([][]bool, l)
    for i := 0; i < l; i++ {
        dp[i] = make([]bool, l)
    }
    max := 1
    begin := 0

    for j := 1; j < l; j ++ {
        for i := 0; i < j; i ++ {
            if i == j {
                dp[i][j] = true
                continue
            }
            if s[i] == s[j] {
                if j - i < 3 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            } else {
                dp[i][j] = false
            }

            if dp[i][j] == true && j - i + 1 > max {
                max = j - i + 1
                begin = i
            }
        }
    }
    return s[begin : begin + max]
}