LeetCode——409.最长回文串_给定一个包含大写字母和小写字母的字符串, 返回 通过这些字母构造成的最长的回文

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:

假设字符串的长度不会超过 1010。
1

示例 1:

输入:
"abccccdd"
1
2

输出:
7
1
2

解释:

我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
1

解法一：

回文串是一个对称的字符串，由n个个数为偶数的字符+对称轴上的任意一个个数为奇数的字符(可以为空)构成，如aabb或aa( c )bb。这意味着我们只需要知道给定字符串中每个字符出现的个数，若为偶数个则直接加在总数count中，若为奇数则将个数减一变成偶数加在总数count中。如果存在奇数则count最后再加一个1表示选定任意一个奇数个数的字符放在对称轴上。

给出的字符串区分大小写，我使用了两个数组分别接收大写和小写字符的个数，然后对数组中的每一个值进行判断，想的有些复杂了，耗时较多

class Solution {
 //创建两个桶分别存放大小写字母
        //ASCII码65-90为A-Z 97-122为a-z
        int[] upperCaseBook=new int[26];
        int[] lowerCaseBook=new int[26];
        char[] chars=s.toCharArray();
        //遍历字符数组
        for(int i=0;i<chars.length;i++){
            //字符为大写
            if(chars[i]<97){
                upperCaseBook[chars[i]-65]++;
            }
            else{
                lowerCaseBook[chars[i]-97]++;
            }
        }
        //分别统计桶中存放偶数个元素的个数的桶的和存奇数个元素的桶
        //桶中为偶数个数则直接加入count，为奇数个数则减一后加入count
        //最后挑选任意一个奇数个数的桶对应的字符作为回文串中间位置的字符串，即最后给count加一个1
        int count=0;
        //判断是否存在奇数，不存在则最后count不用加1
        boolean flag=false;
        for(int i=0;i<26;i++){
          if(upperCaseBook[i]%2==0){
            count=count+upperCaseBook[i];
          }
          if(lowerCaseBook[i]%2==0){
            count=count+lowerCaseBook[i];
          }  
          if(upperCaseBook[i]%2!=0){
            flag=true;
            count+=upperCaseBook[i]-1;
          }
          if(lowerCaseBook[i]%2!=0){
            flag=true;
            count+=lowerCaseBook[i]-1;
          }  
               
        }
        if(flag){
            count+=1;
        }
        return count;
}
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
40
41
42
43
44

解法二

源自LeetCode官方题解：LeetCode题解
这题只需要我们求得最长回文串的个数，并不关注具体的字符串的值，所以并不需要特别去用两个数组存储字符串，只需要创建一个数组能把ASCII码从a-Z的字符都存起来的数组就可以了，甚至不需要特别去考虑这个数组的空间大小为58，直接定义一个大小为128的数组方便存放数据就行了，将奇数个数转化成偶数个数可以通过整除2再乘2的方式得到，这样整个方法j就简单很多了。

class Solution {
    public int longestPalindrome(String s) {
        int[] arr = new int[128];
        for (char c: s.toCharArray()){            
            arr[c]++;
        }
        int count = 0;
        for (int v: arr) {
            count += v / 2 * 2;
            if (v % 2 == 1 && count % 2 == 0){
                count++;
            }           
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

收获

解题时先分析清楚题目的要求，减少不必要的操作