以下代码减少运行时间的最佳解决方案

Question

以下代码用于获取字符串输入并查找其排列是否为回文。该代码需要 o(n) 时间。我希望有更好的解决方案。

public class Solution {

    public static void main(String[] args) {
        Scanner myScan = new Scanner(System.in);
        String str = myScan.nextLine();

        String a = "NO";
        permutation("", str);
        System.out.println(a);
        // Assign ans a value of YES or NO, depending on whether or not inputString satisfies the required condition
        myScan.close();
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        String an = "NO";
        if (n == 0) {
            System.out.println(prefix);
            StringBuffer sb = new StringBuffer(prefix).reverse();
            String str1 = sb.toString();

            if (prefix.equals(str1)) {
                an = "YES";
                System.out.println(an);
                System.exit(0);
            }

        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i),
                  str.substring(0, i) + str.substring(i + 1));
            }
        }
    }
}

Answer 1

（这看起来有点像家庭作业，或者 Java 初学者的私人练习，所以我不想给你完整的代码，而只是给你想法或算法，这样你就可以想出自己实际执行。）

没必要把全部的排列都枚举出来，看看其中一个是不是回文。您需要做的就是统计单词中所有的个字母，看看是否有至多一个字母的出现次数为奇数.以回文 racecar 为例。它可以被看作具有三个部分：rac e car。第一部分和第三部分中的字母相同，因此这些字母中的每一个都必须是偶数。第二部分只有一种字母，但可以重复任意次数。

所以，基本算法是这样的：

创建一个字典，map，用于计算字母，例如HashMap<String, Integer> 在 Java
对于 word 中的每个单独字符，将其在 map 中的计数增加一个
为奇数字母创建一个计数器，例如int odd_letters
对于map中的每个字符，检查其计数是否为奇数，如果是，则将odd_letters计数器加一
如果odd_letters计数器小于或等于1，returntrue，否则returnfalse

如果你还需要知道实际的回文排列，如果有的话，你可以很容易地从计数图中构造一个。

假设我们的单词是 racecar。计数为 {a: 2, c: 2, e: 1, r: 2}

对于每个偶数字母，以任意顺序连接这些字母数字的一半，例如acr
在中间添加奇数字母（如果有的话），与计算的次数相同：acr e
最后，再次添加第一部分，顺序相反：acr e rca

（当然，racecar 本身已经是一个回文，但这没关系；找到一个真正的回文词比找到一个回文排列的词更容易。）

最后，请注意你的代码的复杂度是不是O(n)（假设n 是字符串的长度）。您正在生成所有排列，因此仅此一项就必须至少是 O(n!)，因为有 n! 个排列。

以下代码减少运行时间的最佳解决方案

Optimal Solution for the following code to reduce running time

java

optimization

以下代码减少 运行 时间的最佳解决方案

Optimal Solution for the following code to reduce running time

java

optimization

以下代码减少运行时间的最佳解决方案