Leetcode 409. Longest PalindromeJAVA語言

1

2

3

4

5

6

7

8

9

10

11

12

13

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

<code>This is case sensitive, for example "Aa" is not considered a palindrome here.</code>

<code>Note:</code>

<code>Assume the length of given string will not exceed 1,010.</code>

<code>Example:</code>

<code>Input:</code>

<code>"abccccdd"</code>

<code>Output:</code>

<code>7</code>

<code>Explanation:</code>

<code>One longest palindrome that can be built is "dccaccd", whose length is 7.</code>

題意：求解字元串中能組成的最大回文的長度。

public class Solution {

    public int longestPalindrome(String s) {

        int[] hash1=new int[26];

        int[] hash2=new int[26];

        for(int i=0;i&lt;s.length();i++){

            if(s.charAt(i)&gt;='a' &amp;&amp; s.charAt(i)&lt;='z'){

            hash1[s.charAt(i)-'a']++;

            }else{

                hash2[s.charAt(i)-'A']++;

            }

        }

        int odds=0;

        for(int i=0;i&lt;26;i++){

            if(hash1[i]%2==1)odds++;

            if(hash2[i]%2==1)odds++;

        if(odds==0)return s.length();

        return s.length()-odds+1;

        // int count=0;

        // int maxj=0;

        // int maxi=0;

        // for(int i=0;i&lt;26;i++){

        //     if(hash1[i]%2==0){

        //         count=count+hash1[i];

        //     }else{

        //         if(hash1[i]&gt;maxj){

        //             maxj=hash1[i];

        //         }else{

        //             count=count+hash1[i]-1;

        //         }

        //     }

        //     if(hash2[i]%2==0){

        //         count=count+hash2[i];

        //         if(hash2[i]&gt;maxi){

        //             maxi=hash2[i];

        //             count+=hash2[i]-1;

        // }

        // int flag=Math.min(maxi,maxj);

        // int ret=0;

        // // if(flag==0)

        // // ret=0;

        // // else

        // ret=flag-1;

        // return count+Math.max(maxi,maxj)+ret;

    }

}

PS:

1、回文串左右對稱，出現次數為偶數的肯定可以。

2、首先統計各個字母（區分大小寫）的出現次數

3、出現次數為偶數的直接加到回文串長中。

4、出現次數為奇數的，最後隻取最長的那一個全部加到回文串長中，其餘的奇數的字母要全部減去1變成偶數。這也是一開始算錯的地方。

是以如果沒有出現次數為奇數的字母，直接傳回字元串長；

有奇數次的字母出現，由于4，我們最後直接傳回字元串長-奇數的個數+1;

+的1是最後的中心點~~~~。

上面的解法簡介明了，不像我一開始的各種情況統計，麻煩。。。。。。。。。。。。。。。。。。

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1890895