本系列導航：劍指offer（第二版）java實現(xiàn)導航帖
面試題：字符串的組合
題目要求：
輸入一個字符串，打印出該字符串中字符的所有組合。如輸入abc坟比，則打印a芦鳍，b，c葛账，ab柠衅，ac，bc籍琳，abc菲宴。
解題思路：
這道題目是在38題.字符串的排列的擴展部分出現(xiàn)的。排列的關鍵在于次序趋急，而組合的關鍵在于狀態(tài)喝峦，即該字符是否被選中進入組合中。
對于無重復字符的情況呜达，以a,b,c為例谣蠢，每一個字符都有兩種狀態(tài)：被選中、不被選中查近；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(不被選中) => 空(不作為一種組合情況)
對于有重復字符的情況霜威，不重復的字符各有兩種狀態(tài)谈喳；而重復的字符狀態(tài)個數(shù)與重復次數(shù)有關。以a,a,b為例戈泼，b有兩種狀態(tài)：被選中婿禽、不被選中，a,a有三種狀態(tài)：被選中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(不被選中) => 空(不作為一種組合情況)
上述無重復字符的情況可以看作是有重復字符的情況的特例，因此琼牧，僅實現(xiàn)有重復字符的字符串組合處理思路即可恢筝。
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{
//先計算出重復次數(shù)
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
