Longest Palindrome go语言实现

Longest Palindrome

题目描述

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

原串是回文的思路（理解错题了）：

• 递归所有子树，或者对子串的始终点动态规划。
• 判断dp[i][j]要用到原来的结果dp[i+1][j-1]，用动态规划。从下往上填，从左往右填。
• 填表顺序：并不是一般的先填边界，而是先填dp[i][i]和dp[i][i+1]。

解：

//原串是回文的写法
func longestPalindrome(s string) int {
    sSlice := []rune(s)
    dp := make([][]bool,len(s),len(s))
    maxLen := 0
    for idx,_ := range dp{
        dp[idx] = make([]bool,len(s),len(s))
    }
    for i:=0;i<len(sSlice);i++{
        dp[i][i] = true
        maxLen = 1
    }
    if len(sSlice)>1{
        for i:=0;i<len(sSlice)-1;i++{
            if sSlice[i] == sSlice[i+1] {
                dp[i][i+1] = true
                maxLen = 2
            }
        }
    }
    if len(sSlice) >= 3{
        for i:=len(sSlice)-3;i>=0;i--{
            for j:=i+2;j< len(sSlice) ;j++ {
                if sSlice[i] == sSlice[j] && dp[i+1][j-1] == true{
                    dp[i][j] = true
                    if j-i+1 > maxLen  {
                        maxLen = j-i+1
                    }
                }
            }
        }
    }
    return maxLen
}

可构成回文串的思路（原题意）：

• 贪心算法。统计字符出现次数。成对计数，再补一个奇数字符。

解：

func longestPalindrome(s string) int {
    sSlice := []rune(s)
    count := make([]int,128)
    for _,elem := range sSlice{
        count[elem]++
    }
    res := 0
    for _,elem := range count{
        res += elem/2*2
        if res%2 == 0 && elem%2 == 1{
            res++
        }
    }
    return res
}