最长回文字符串

标签:pen   转移   eset   回文   rgba   tco   htm   ali   make   

题目来源:https://leetcode-cn.com/problems/longest-palindromic-substring/submissions

思路:动态规划(参看官方解析)

关键点:

1:对于字符串长度大于2,状态转移方程:P(i,j)=P(i+1,j?1) && (Si?==Sj?

2:边界条件:子串的长度为 1 或 2。对于长度为 1 的子串,它显然是个回文串;对于长度为 2 的子串,只要它的两个字母相同,它就是一个回文串。

1        
x 1      
x x 1    
x x x 1  
x x x x 1

 

3:遍历下三角即可以求出最大回文字符串

go代码:

package main

func longestPalindrome(s string) string {

    ans:=""
    max:=0
    n := len(s)
    dp := make([][]bool, n) //dp[i][j] 表示string [i,j]是回文字符串
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
    }


    //P(i,j) = P(i+1,j?1)^(Si ==S /j)
    for j:=0; j<n; j++  {
        for i:=0; i<=j; i++  {
            if j == i {
                dp[j][i] = true
            }else if j - i == 1 {
                if s[j] == s[i] {
                    dp[j][i] = true
                }
            }else {
                dp[j][i] = (s[j] == s[i]) && (dp[j-1][i+1])
            }
            if dp[j][i] &&  max <= (j-i){
                max = j-i
                ans = s[i:j+1]
            }
        }
    }
    return ans
}


func main() {
    println(longestPalindrome("a"))
}

 

 

 

最长回文字符串

标签:pen   转移   eset   回文   rgba   tco   htm   ali   make   

原文地址:https://www.cnblogs.com/iuyy/p/14129159.html

版权声明:完美者 发表于 2020-12-18 12:45:33。
转载请注明:最长回文字符串 | 完美导航

暂无评论

暂无评论...