试图找到此输入的最长回文

Question

给定一个由小写或大写字母组成的字符串，找出可以用这些字母组成的最长回文的长度。

这是区分大小写的，例如"Aa"在这里不被认为是回文。

注：

Assume the length of given string will not exceed 1,010.

示例：

输入："abccccdd"

输出：7

解释：

One longest palindrome that can be built is "dccaccd", whose length is 7.

我的代码适用于 "abccccdd" 和 "banana" 等简单输入，但对 "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth" 无效。我不确定如何调试它。

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] carr = s.toCharArray();
        Arrays.sort(carr);
        int leftInd = 0;
        int rightInd = 0;
        for(int i=0; i<carr.length; i++){
            if(map.containsKey(carr[i]))
                continue;
            else
                map.put(carr[i], 1);
        }
        for(int i=0; i<carr.length-1; i++){
            for(int j=i+1; j<carr.length; j++){
                if(carr[i]==carr[j]){
                    if(map.get(carr[i])==null)
                        continue;
                    carr[j] = Character.MIN_VALUE;
                    int count = map.get(carr[i]);
                    map.put(carr[i], count + 1);
                }
            }
        }
        int ans = 0;
        int[] oddValArr = new int[map.size()];
        int oddInd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if(value % 2 == 0){
                ans += value;
            }
            else{
                oddValArr[oddInd] = value;
                oddInd++;
            }
        }
        int biggestOddNum = 0;
        for(int i=0; i<oddValArr.length; i++){
            if(oddValArr[i] > biggestOddNum)
                biggestOddNum = oddValArr[i];
        }
        return ans + biggestOddNum;
     }
}

输出 655

预计 983

Answer 1

你的错误在于，你只使用 oddValArr 中最大的 个奇数组。例如输入"aaabbb"，最大的回文是"abbba"，所以组a的长度为3，为奇数，我们用3 - 1 = 2 个字母。

此外，那些嵌套的 for 循环可以用一个 for 替换，使用 Map:

public int longestPalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();  // letter groups
    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i));
        if(map.containsKey(c))
            map.put(c, map.get(i) + 1);
        else
            map.put(c, 1);
    }

    boolean containsOddGroups = false;
    int ans = 0;
    for(int count : map.values()){
        if(count % 2 == 0)  // even group
            ans += count;
        else{  // odd group
            containsOddGroups = true;
            ans += count - 1;
        }
    }
    if(!containOddGroups)
        return ans;
    else
        return ans + 1;  // we can place one letter in the center of palindrome
}

Answer 2

你快到了，但是把它复杂化了很多。我的解决方案几乎只从您的解决方案中删除代码：

public static int longestPalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();
    char[] carr = s.toCharArray();
    for (int i = 0; i < carr.length; i++) {
        if (map.containsKey(carr[i]))
            map.put(carr[i], map.get(carr[i]) + 1);
        else
            map.put(carr[i], 1);
    }

    int ans = 0;
    int odd = 0;
    for (Integer value : map.values()) {
        if (value % 2 == 0) {
            ans += value;
        } else {
            ans += value - 1;
            odd = 1;
        }
    }
    return ans + odd;
}

解释：

第二个循环连同排序已被删除 - 它已合并到第一个循环中。根本不需要排序。
然后你迭代一个角色出现的频率
- 如果是偶数你像以前一样增加ans
- 如果是奇数你可以用它的count - 1个字符来组成偶数长度的回文
如果您发现至少一个奇数出现，您可以将那个奇数字符放在回文的中心并将其长度增加一个

试图找到此输入的最长回文

Trying to find the longest palindrome for this input

java

palindrome