最长回文串（Java实现）

缺乏、安全感 2023-07-17 02:43 9阅读 0赞

## 最长回文串（Java实现） ##

题目：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。  
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。  
注意:  
假设字符串的长度不会超过 1010。

示例 1:

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

我的思路是：  
利用HashMap将字符串中出现的字符和出现的次数保存起来，根据回文串的规律，奇数次的字符只能出现一次，然后构造了两个ArrayList，一个用于存放奇数次的字符的次数，另外一个用于存放偶数次的字符的次数，根据三种情况：

*  既有奇数次字符，也有偶数次字符，如“abccccdd”，那么两个ArrayList肯定不为空，oddList（奇数数组）中的元素为\[1,1\]，evenList（偶数数组）中的元素为\[4,2\]，根据回文串的规律可知，最长回文串的长度应该为 \[(1-1)+(1-1)+1\]+\[4+2\]=7；
 *  只有奇数次字符，如“bbb”，那么evenList（偶数数组）为空，oddList（奇数数组）中的元素为\[3\]，根据回文串的规律可知，最长回文串的长度应该为 3-1+1=3；
 *  只有偶数次字符，如“bb”，那么oddList（奇数数组）为空，evenList（偶数数组）中的元素为\[2\]，根据回文串的规律可知，最长回文串的长度应该为 2.

代码实现之：

package Day46;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    /** * @Author Zhongger * @Description 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 * 注意: * 假设字符串的长度不会超过 1010。 * @Date 2020.3.19 */
    public class longestPalindromeSolution { 
        public static void main(String[] args) { 
            System.out.println(new longestPalindromeSolution().longestPalindrome("abccccdd"));
        }
        public int longestPalindrome(String s) { 
            if (s.length()<=0||s.length()>1010){ 
                return 0;
            }
            HashMap<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) { //利用HashMap将字符串中出现的字符和出现的次数保存起来
                char c = s.charAt(i);
                if (map.get(c)==null){ 
                    map.put(c,1);
                }else { 
                    map.put(c,map.get(c)+1);
                }
            }
            int count=0;
            Iterator<Map.Entry<Character, Integer>> iterator = map.entrySet().iterator();
            ArrayList<Integer> oddlist = new ArrayList<>();
            ArrayList<Integer> evenlist = new ArrayList<>();
            while (iterator.hasNext()){ 
                Integer value = iterator.next().getValue();
                if (value%2==1){ //奇数
                    oddlist.add(value);
                }else { //偶数
                    evenlist.add(value);
                }
            }
            if (!oddlist.isEmpty()&&!evenlist.isEmpty()){ 
                for (Integer odd:oddlist) { 
                    odd=odd-1;
                    count=count+odd;
                }
                count+=1;
                for (Integer even : evenlist) { 
                    count=count+even;
                }
            }
            if (oddlist.isEmpty()){ 
                for (Integer even : evenlist) { 
                    count=count+even;
                }
            }
            if (evenlist.isEmpty()){ 
                for (Integer odd:oddlist) { 
                    odd=odd-1;
                    count=count+odd;
                }
                count+=1;
            }
            return count;
        }
    }

虽然在LeetCode上AC了，但这显然不是最好的解法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
本人比较菜，第一次是没把问题考虑全导致错误。

来看看官网的解法：  
方法一：贪心  
思路

回文串是一个正着读和反着读都一样的字符串。以回文中心为分界线，对于回文串中左侧的字符 ch，在右侧对称的位置也会出现同样的字符。例如在字符串 “abba” 中，回文中心是 “ab|ba” 中竖线的位置，而在字符串 “abcba” 中，回文中心是 “ab©ba” 中的字符 “c” 本身。我们可以发现，在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次。

那么我们如何通过给定的字符构造一个回文串呢？我们可以将每个字符使用偶数次，使得它们根据回文中心对称。在这之后，如果有剩余的字符，我们可以再取出一个，作为回文中心。

算法

对于每个字符 ch，假设它出现了 v 次，我们可以使用该字符 v / 2 \* 2 次，在回文串的左侧和右侧分别放置 v / 2 个字符 ch，其中 / 为整数除法。例如若 “a” 出现了 5 次，那么我们可以使用 “a” 的次数为 4，回文串的左右两侧分别放置 2 个 “a”。

如果有任何一个字符 ch 的出现次数 v 为奇数（即 v % 2 == 1），那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。在代码中，我们用 ans 存储回文串的长度，由于在遍历字符时，ans 每次会增加 v / 2 \* 2，因此 ans 一直为偶数。但在发现了第一个出现次数为奇数的字符后，我们将 ans 增加 1，这样 ans 变为奇数，在后面发现其它出现奇数次的字符时，我们就不改变 ans 的值了。

class Solution { 
        public int longestPalindrome(String s) { 
            int[] count = new int[128];
            for (char c: s.toCharArray())
                count[c]++;
    
            int ans = 0;
            for (int v: count) { 
                ans += v / 2 * 2;
                if (v % 2 == 1 && ans % 2 == 0)
                    ans++;
            }
            return ans;
        }
    }

复杂度分析

时间复杂度：O(N)O(N)，其中 NN 为字符串 s 的长度。我们需要遍历每个字符一次。

空间复杂度：O(S)O(S)，其中 SS 为字符集大小。在 Java 代码中，我们使用了一个长度为 128 的数组，存储每个字符出现的次数，这是因为字符的 ASCII 值的范围为 \[0, 128)。而由于题目中保证了给定的字符串 s 只包含大小写字母，因此我们也可以使用哈希映射（HashMap）来存储每个字符出现的次数，例如 Python 和 C++ 的代码。如果使用哈希映射，最多只会存储 52 个（即小写字母与大写字母的数量之和）键值对。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20230528/fc646f4304ef418baf7189fcce79e3ea.png