查找字符串的最大回文长度

忘是亡心i 2021-06-24 15:56 480阅读 0赞

查找字符串的最大回文长度的两种算法：  
第一中方法：

public class Solution { 
        /** * @param s a string which consists of lowercase or uppercase letters * @return the length of the longest palindromes that can be built */
        public int longestPalindrome(String s) {
            //最长长度
            int k = 0;
            int i = s.length();
            List list = new ArrayList();
            Map map = new HashMap();
            for (int j = 0; j < i; j++) {
                if (!list.contains(s.charAt(j))) {
                    list.add(s.charAt(j));
                    //计算该字符出现了多少次
                    Integer b = 1;
                    for (int a = j + 1; a < i; a++) {
                        if (s.charAt(j) == s.charAt(a)) {
                            b = b + 1;
                        }
                    }
                    map.put(s.charAt(j), b);
                }
            }
            //还没计算只有一个元素的字符
            boolean isF = true;
            Set set = map.keySet();
            for (Object object : set) {
                int sum = Integer.valueOf(map.get(object).toString());
                if (sum == 1 && isF) {
                    k = k + 1;
                    isF = false;
                } else if (sum > 1) {
                    if (set.size() == 1) {
                        k = k + sum;
                    } else {
                        //大于1的部分取偶数
                        k = k + (sum / 2) * 2;
                    }
                }
            }
            return k;
        }
    }

第二种方法：考虑到时间和空间复杂度，建议用第二种方法！！！

public class Solution { 
        /** * @param s a string which consists of lowercase or uppercase letters * @return the length of the longest palindromes that can be built */
        public int longestPalindrome(String s) {
            String str = s;
            int i = str.length();
            char[] chars = new char[128];
            for (int a = 0; a < i; a++) {
                chars[str.charAt(a)]++;
            }
            boolean isF = true;
            int k = 0;
            for (int b = 0; b < 127; b++) {
                if (chars[b] > 0) {
                    if (chars[b] % 2 != 0) {
                        //只允许出现一个奇数
                        if (isF) {
                            k++;
                            isF = false;
                        }
                        //如果该字符是只出现一次，要不就在上面算过了，要不就已经有奇数了，所以不能算
                        if (chars[b] != 1) {
                            k = k + (chars[b] / 2) * 2;
                        }
                    } else if (chars[b] % 2 == 0) {
                        k = k + chars[b];
                    }
                }
            }
            return k;
        }
    }