面试题：字符串的组合
题目要求：
输入一个字符串，打印出该字符串中字符的所有组合。如输入abc，则打印a，b，c，ab，ac，bc，abc。
解题思路：
这道题目是在38题.字符串的排列的扩展部分出现的。排列的关键在于次序，而组合的关键在于状态，即该字符是否被选中进入组合中。
对于无重复字符的情况，以a,b,c为例，每一个字符都有两种状态：被选中、不被选中；2*2*2=8，再排除为空的情况，一共有7种组合：
a(被选中)b(被选中)c(被选中) => abc
a(被选中)b(被选中)c(不被选中) => ab
a(被选中)b(不被选中)c(被选中) => ac
a(被选中)b(不被选中)c(不被选中) => a
a(不被选中)b(被选中)c(被选中) => bc
a(不被选中)b(被选中)c(不被选中) => b
a(不被选中)b(不被选中)c(被选中) => c
a(不被选中)b(不被选中)c(不被选中) => 空(不作为一种组合情况)
对于有重复字符的情况，不重复的字符各有两种状态；而重复的字符状态个数与重复次数有关。以a,a,b为例，b有两种状态：被选中、不被选中，a,a有三种状态：被选中2个，被选中1个，不被选中。2*3=6，排除为空的情况，一共有5种组合：
a(被选中2个)b(被选中) => aab
a(被选中2个)b(不被选中) => aa
a(被选中1个)b(被选中) => ab
a(被选中1个)b(不被选中) => a
a(不被选中)b(被选中) => b
a(不被选中)b(不被选中) => 空(不作为一种组合情况)
上述无重复字符的情况可以看作是有重复字符的情况的特例，因此，仅实现有重复字符的字符串组合处理思路即可。
package chapter4;
import java.util.*;
/**
* Created by ryder on 2017/7/22.
* 字符串的组合
*/
public class P199_StringCombination {
//无重复字符：对于每一个字符，都由两种选择：被选中、不被选中；
//有重复字符：整体需要先排序，对于重复n遍的某种字符，有如下选择：不被选中，选1个，选2个...选n个。
public static List<char[]> combination(char[] strs) {
if (strs == null || strs.length == 0)
return null;
Arrays.sort(strs);
List<char[]> ret = new LinkedList<>();
combinationCore(strs,ret,new StringBuilder(),0);
return ret;
}
public static void combinationCore(char[] strs,List<char[]> ret,StringBuilder stringBuilder,int cur){
if(cur==strs.length ) {
if(stringBuilder.length()>0)
ret.add(stringBuilder.toString().toCharArray());
}
else if(cur+1==strs.length||strs[cur]!=strs[cur+1]){
combinationCore(strs,ret,stringBuilder.append(strs[cur]),cur+1);
stringBuilder.deleteCharAt(stringBuilder.length()-1);
combinationCore(strs,ret,stringBuilder,cur+1);
}
else{
//先计算出重复次数
int dumplicateStart = cur;
while(cur!=strs.length&&strs[dumplicateStart]==strs[cur]){
stringBuilder.append(strs[cur]);
cur++;
}
int newStart = cur;
while (cur>=dumplicateStart) {
combinationCore(strs, ret, stringBuilder, newStart);
if(cur!=dumplicateStart)
stringBuilder.deleteCharAt(stringBuilder.length() - 1);
cur--;
}
}
}
public static void main(String[] args) {
char[] strs2 = {'a', 'a', 'b'};
List<char[]> ret2 = combination(strs2);
for (char[] item : ret2) {
for (int i = 0; i < item.length; i++)
System.out.print(item[i]);
System.out.println();
}
}
}
运行结果
aab
aa
ab
a
b
网友评论