我阅读了生成字符串所有排列 (solution) 问题的解决方案。
谁能解释一下 perm2 与 perm1 有何不同? (我觉得唯一的区别是perm1试图把每个元素放在第一个位置,而perm2放在最后一个)
// print N! permutation of the characters of the string s (in order)
public static void perm1(String s) { perm1("", s); }
private static void perm1(String prefix, String s) {
int N = s.length();
if (N == 0) System.out.println(prefix);
else {
for (int i = 0; i < N; i++)
perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
}
}
// print N! permutation of the elements of array a (not in order)
public static void perm2(String s) {
int N = s.length();
char[] a = new char[N];
for (int i = 0; i < N; i++)
a[i] = s.charAt(i);
perm2(a, N);
}
private static void perm2(char[] a, int n) {
if (n == 1) {
System.out.println(a);
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n-1);
perm2(a, n-1);
swap(a, i, n-1);
}
}
另外,如果字符串中某些字母相同,那么某些排列也会相同?我能想到的防止这种情况的唯一方法是将结果保存在哈希集中,以便只保留一个排列实例。有更好的解决方案吗?
最佳答案
我希望第二种解决方案的理由是效率。它使用字符数组而不是 String 对象,并在每一步交换字符,而不是通过连接创建新的 String。
就功能而言,两种解决方案之间的唯一区别是结果输出的顺序。
你是对的,如果输入中有一些重复的字符,这并不能保证唯一的解决方案。如果需要,存储结果和检查唯一性(通过使用 Set 或直接通过 contains
)将是避免这种情况的最简单方法。
在第二种解决方案中,另一种方法是检查字符是否已被处理。这将避免存储结果集的开销(这对于长字符串可能很重要)。
在第二个 perm2
函数中:
if (n == 1) {
System.out.println(a);
return;
}
for (int i = n; i < a.length; i++) {
if (a[i] == a[n-1])
return;
}
for (int i = 0; i < n; i++) {
boolean duplicate = false;
for (int j = 0; !duplicate && j < i; j++)
duplicate = a[i] == a[j];
if (!duplicate) {
swap(a, i, n-1);
perm2(a, n-1);
swap(a, i, n-1);
}
}
关于java - 不重复的字符串的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28206047/