在下面的代码中，我找到给定输入字符串的所有可能排列并将它们存储在列表中，然后计算其中的回文。当输入字符串长度小于 10 时，这工作正常。但是当输入字符串时length 大于 10，则需要花费大量时间来查找排列。我想知道这里可以优化什么以获得恒定的执行时间？
private static char[] inputArray;
private static List<String> listOfpermutations = new ArrayList<>();
private static int count;
public static void main(String s[]) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input = reader.readLine();
inputArray = input.toCharArray();
permutation(0);
for (String combination : listOfpermutations) {
if (combination.equals(new StringBuilder(combination).reverse().toString())) {
count++;
}
}
System.out.println(count);
}
public static void permutation(int start)
{
String temp = "";
if (start != 0) {
if (start == inputArray.length) {
for (int i = 0; i < start; i++) {
temp = temp + inputArray[i];
}
if (!listOfpermutations.contains(temp)) {
listOfpermutations.add(temp);
}
}
}
for (int i = start; i < inputArray.length; i++)
{
swap(start, i);
permutation(start + 1);
swap(start, i);
}
}
static void swap(int pos1, int pos2) {
char temp = inputArray[pos1];
inputArray[pos1] = inputArray[pos2];
inputArray[pos2] = temp;
}
测试输入:
- aaabbb//效果棒极了
- ccccddddcc//工作正常
- ccccddddcce//这里花费的时间太长了
最佳答案
IMO 这与其说是算法问题，不如说是数学问题。
由于您只对回文字符串的数量感兴趣，因此无需生成所有可能的排列。
计算字符串中每种类型的字符个数。将字符一分为二。计算该半串的排列数。这就是答案，因为字符串的另一半只是这一半的镜像。
例如，如果字符串是 aabbcc，则 a 的计数 = 2，b 的计数 = 2，c 的计数 = 2。
所以我们将这些减半以形成 abc，以 6 种方式排列它。这将是回文的排列数。
(需要检查字符串中的字符数是奇数还是偶数)
关于java - 查找给定字符串排列的优化算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20544611/