在我开始之前,我必须为提出另一个重复排列的案例而道歉。我已经浏览了大部分搜索结果,但无法真正找到我要查找的内容。我已阅读有关词典顺序的信息并已实施。对于这个问题,我想实现一个递归方法,它打印出所有长度为 n 的字符串,该字符串仅由具有相同数量的 a 和 b 的字符 a 和 b 组成。字符串必须按词汇顺序一次打印出一行。因此,例如,一个电话:
printBalanced(4);
将打印字符串:
aabb
abab
abba
baab
baba
bbaa
这是代码
public static void main(String[] args){
printBalanced(4);
}
public static void printBalanced(int n){
String letters = "";
//string to be duplicates of "ab" depending the number of times the user wants it
for(int i =0; i<n/2;i++){
letters += "ab";
}
balanced("",letters);
}
private static void balanced(String prefix, String s){
int len = s.length();
//base case
if (len ==0){
System.out.println(prefix);
}
else{
for(int i = 0; i<len; i++){
balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));
}
}
}
我的打印结果:
abab
abba
aabb
aabb
abba
abab
baab
baba
baab
baba
bbaa
bbaa
aabb
aabb
abab
abba
abab
abba
baba
baab
bbaa
bbaa
baab
baba
如您所见,我得到了很多重复项。这部分是由于要求仅使用字符“a”和“b”。如果它是“abcd”或“0123”,则不会发生重复。我已经阅读了有关使用数组列表并存储所有结果的信息,然后循环遍历 N 个元素以检查重复项,然后将其删除。这似乎不是最好的方法。有人可以分享有关此问题的其他更好的解决方案吗?=)
我使用 SortedSet 的解决方案:
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
public class BalancedStrings {
public static void main(String[] args){
printBalanced(4);
}
public static void printBalanced(int n){
String letters = "";
for(int i =0; i<n/2;i++){
letters += "ab";
}
SortedSet<String> results = balanced("",letters);
Iterator<String> it = results.iterator();
while (it.hasNext()) {
// Get element and print
Object element = it.next();
System.out.println(element);
}
}
//This method returns a SortedSet with permutation results. SortedSet was chosen for its sorting and not allowing
//duplicates properties.
private static SortedSet<String> balanced(String prefix, String s){
SortedSet<String> set = new TreeSet<String>();
int len = s.length();
//base case
if (len == 0){
//return the new SortedSet with just the prefix
set.add(prefix);
return set;
}
else{
SortedSet<String> rest = new TreeSet<String>();
for(int i = 0; i<len; i++){
//get all permutations and store in a SortedSet, rest
rest = balanced(prefix + s.charAt(i),s.substring(0,i)+s.substring(i+1,len));
//put each permutation into the new SortedSet
set.addAll(rest);
}
return set;
}
}
}