算法-Hash-回文

谁借莪１个温暖的怀抱￠ 2023-03-13 03:17 15阅读 0赞

# 算法-Hash-回文 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/longest-palindrome

## 1.2 题目描述 ##

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

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

注意:  
假设字符串的长度不会超过 1010。

示例 1:

输入:  
“abccccdd”

输出:  
7

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

# 2 HashMap #

# 2.1 思路 #

1.  用HashMap存储每个字符的出现次数是奇数或偶数。
2.  当是偶数时，将回文累积长度加2，并将奇数个数减1；
3.  奇数时，仅将累积的奇数个数加1.
4.  最后，判断奇数个数，如果大于0，就将回文累积长度加1即可得到答案。

## 2.2 代码 ##

class Solution { 
        public int longestPalindrome(String s) { 
            if(s == null){ 
                return 0;
            }
            if(s.length() < 2){ 
                return s.length();
            }
            Map<String,Boolean> cntMap = new HashMap<>(s.length());
            String[] strArray = s.split("");
            int result = 0;
            int oddCnt = 0;
            for(String str : strArray){ 
                Boolean odd = cntMap.get(str);
                if(odd != null && odd == true){ 
                    result = result + 2;
                    cntMap.put(str, false);
                    oddCnt--;
                }else{ 
                    cntMap.put(str, true);
                    oddCnt++;
                }
            }
            if(oddCnt > 0){ 
                result++;
            }
            return result;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200510132144294.png]  
O(N)

*  但是为啥这么慢呢？

## 2.4 空间复杂度 ##

O(N)

# 3 char+数组 #

# 3.1 思路 #

前面使用HashMap，内部使用了Java包装对象，所以速度很慢。

因为是需要计算字符串内部每个char的出现次数，所以可以使用一个数组来存char对应ascii码出现次数是奇数还是偶数。

## 3.2 代码 ##

if(s == null){ 
                return 0;
            }
            if(s.length() < 2){ 
                return s.length();
            }
            // ascii码一共256字符
            // 为0时表示当前该字符出现次数为偶数或没有出现过，
            // 为1时表示出现过奇数次
            int[] cntArray = new int[256];
            char[] charArray = s.toCharArray();
            int result = 0;
            int oddCnt = 0;
            for(char c : charArray){ 
                int flag = cntArray[c];
                if(flag != 0){ 
                    result = result + 2;
                    cntArray[c] = 0;
                    oddCnt--;
                }else{ 
                    cntArray[c] = 1;
                    oddCnt++;
                }
            }
            if(oddCnt > 0){ 
                result++;
            }
            return result;
        }
    }

## 3.3 时间复杂度 ##

O(N)  
![在这里插入图片描述][2020051013282481.png]

## 3.4 空间复杂度 ##

O(N)

[20200510132144294.png]: /images/20230312/447152632fc041a6b92a98c57cc66dcd.png
[2020051013282481.png]: /images/20230312/ff7e78ab25394a1fb57b51b276c71e94.png