輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。 結(jié)果請按字母順序輸出。
采用遞歸的思想：
把需要全排列的字符串分為兩部分看待：
（1）字符串的第一個(gè)字符；
（2）第一個(gè)字符后面的所有字符；
求所有可能出現(xiàn)在第一個(gè)位置的字符；將第一個(gè)字符和后面的字符一次交換；
固定第一個(gè)字符，對第一個(gè)字符后面的所有字符求全排列。第一個(gè)字符后面的所有字符又可以分為兩部分；
java代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.util.ArrayList; import java.util.TreeSet; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<String>(); if(str==null||str.length()==0) { return res; } char[] charArray = str.toCharArray(); //輸出按照輸入字典順序 TreeSet<String> tempRes = new TreeSet<String>(); PermutationCore(charArray,tempRes,0); res.addAll(tempRes); return res; } private void PermutationCore( char[] charArray,TreeSet<String> tempRes,int loc) { if(charArray==null || charArray.length==0 || loc<0 || loc>charArray.length-1) { return ; } if(loc==charArray.length-1) { tempRes.add(String.valueOf(charArray));//遞歸的出口 } else { for(int i=loc;i<charArray.length;i++) { swap(charArray,i,loc);//將第一個(gè)字符與后面的字符交換 PermutationCore(charArray,tempRes,loc+1);//對后面所有的字符進(jìn)行全排列 swap(charArray,i,loc);//再將之前交換的字符交換回來，以便第一個(gè)字符再與其他字符交換 } } } private void swap(char[] charArray,int i,int j) { char temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp; } } |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/snow_7/article/details/52459324
