day 49 | 647. 回文子串 ● 516.最长回文子序列

647. 回文子串

dp含义：dp如果是表示i-j的序列中回文子串的个数的话，当新来一个后只能判定出来是整体的回文，内部的无法判断，所以用bool表示整体比较恰当。
递推公式：由于i，j是由i+1,j-1决定的，所以相当于是从右下开始遍历
初值：开始时必然都是false

func countSubstrings(s string) int {
    dp := make([][]bool, len(s) + 1)
    for i := 0; i < len(dp);i++{
        dp[i] = make([]bool, len(s) + 1)
    }
    res := 0
    for i := len(s); i >= 1; i--{
        for j := i; j <= len(s); j++{
            if s[i - 1] == s[j - 1]{
                if j - i <= 1{
                    res++
                    dp[i][j] = true
                }else if dp[i + 1][j - 1]{
                    res++
                    dp[i][j] = true
                }
            }
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

516.最长回文子序列

dp数组（dp table）以及下标的含义
dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

func longestPalindromeSubseq(s string) int {
    dp := make([][]int, len(s))
    for i := 0; i < len(s); i++{
        dp[i] = make([]int, len(s))
        dp[i][i] = 1
    }

    for i := len(s) - 1; i >= 0; i--{
        for j := i+1; j < len(s); j++{
            if s[i] == s[j]{
                dp[i][j] = dp[i + 1][j - 1] + 2
            }else{
                dp[i][j] = max(dp[i][j - 1], dp[i+1][j])
            }
        }
    }
    return dp[0][len(s) - 1]
}
func max(a, b int)int{
    if a < b{
        return b
    }else{
        return a
    }
}
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