java - 排列单词形成回文

Question

你好，我一直在尝试从这个输入中形成回文:

String[] text ={"ivcci", "oyotta", "cecarar","bbb","babbbb"};
getPalindrome(text);

我需要重新排列数组中的所有单词以产生此输出

civic
-1
rececar
bbb
bbabb

该方法期望接收一个字符串数组，如

public static String getPalindrome(String[] text){}

“返回 -1 表示数组中的 i.g “oyotta” 无法形成回文

我一直在测试这段代码，它可以工作，但是“cecarar”没有生成“racecar”，因为我在 java 中有点新，我使用了一个字符串而不是一个字符串数组，任何人都可以帮助正确编写这段代码好吗？

非常感谢!

public static String getPalindrome(String s) {

    if (s == null)
        return null;
    Map<Character, Integer> letters = new HashMap<Character, Integer>();

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!letters.containsKey(c))
            letters.put(c, 1);
        else
            letters.put(c, letters.get(c) + 1);
    }

    char[] result = new char[s.length()];
    int i = 0, j = result.length - 1;
    Character middle = null;
    for (Entry<Character, Integer> e : letters.entrySet()) {
        int val = e.getValue();
        char c = e.getKey();

        if (val % 2 != 0) {
            if (middle == null && s.length() % 2 != 0) {
                middle = c;
                val--;
            } else
                return "-1";
        }
        for (int k = 0; k < val / 2; k++) {
            result[i++] = c;
            result[j--] = c;
        }
    }
    if (middle != null)
        result[result.length / 2] = middle;
    return new String(result);
}

Answer 1

为了使一组字符能够产生回文，只有一个字母可以重复奇数次，因此您可以先将其剔除。

无需为您编写实际代码，以下是我将使用的算法:

创建字符到计数器的映射。可以做 int[] counts = new int[26]; 遍历输入字符串中的每个字符，并增加计数:++counts[Character.toLower(c)-'a']; 然后遍历每个字符，看看它的奇数 if (counts[i] & 1 != 0) { if (oddIndex != -1) { return -1; } 奇指数=我; } 如果有两个或多个奇数，这将返回 -1。 然后，您可以创建一个 StringBuilder，并从中间的 oddIndex 开始(如果它存在)。 然后检查计数，并将 count[i]/2 添加到字符串构建器的前面和后面。

这将为您提供来自原始输入的对称字符串。

现在，如果您确实需要单词，那么您必须有一本回文字典。您实际上可以对所有回文进行预处理以获得“已排序字符串”=>“回文”的映射

class PalindromeChecker
{
    final Map<String, String> palindromes = new HashMap<String, String>();

    public PalindromeChecker(Iterable<String> allPalindromes) {
        for (String palindrome: allPalindromes) {
           char[] chars = palindrome.getChars();
           Arrays.sort(chars);
           palindromes.put(String.valueOf(chars), palindromes);
        }
    }

    public String getPalindrome(String input) {
           char[] chars = input.getChars();
           Arrays.sort(chars);

           return palindromes.get(String.valueOf(chars));
    }
}