在我开始之前,我必须为提出另一个有重复排列的情况道歉。我已经浏览了大部分搜索结果,但实际上并没有找到我想要的。我已经阅读了关于字典序的文章并进行了实现。对于这个问题,我应该实现一种递归方法,打印出所有长度为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",就不会有重复。我已经阅读了关于使用ArrayList并存储所有结果,然后循环遍历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;
}
}
}