剑指Offer:字符串的排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

分析

整个字符串的排列可以看成两步。第一步求出所有出现在第一个位置的字符,即把第一个字符和后面的所有字符交换。第二步固定第一个字符,求后面所有字符的排列,这时候我们仍把后面的字符分成两部分。然后一直进行下去。

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
import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
public static void swap(char[] ch, int i, int j) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}

public static void Permutation(char[] ch, int begin, TreeSet<String> treeSet) {
if(ch==null || ch.length==0 || begin<0 || begin>ch.length-1) {
return ;
}

if (begin == ch.length-1) {
treeSet.add(String.valueOf(ch));
}else {
for (int i = begin; i < ch.length; i++) {
swap(ch, begin, i);
Permutation(ch, begin+1, treeSet);
swap(ch, begin, i);
}
}
}

public static ArrayList<String> Permutation(String str) {
ArrayList<String> arrayList = new ArrayList<>();
if (str == null || str.length() == 0)
return arrayList;
TreeSet<String> treeSet = new TreeSet<>();
Permutation(str.toCharArray(), 0, treeSet);
arrayList.addAll(treeSet);
return arrayList;
}
}
请我一杯酸奶?
------ 本文结束感谢您的阅读-------------
0%