描述
输入一个字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例1
输入:”ab”
返回值:[“ab”,”ba”]
说明:
返回[“ba”,”ab”]也是正确的
示例2
输入:”aab”
返回值:[“aab”,”aba”,”baa”]
示例3
输入:”abc”
返回值:[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
第一种解决方法,对于一个长度为n的字符串来说,它所有字符的排列组合数量为 n!(n*(n-1)…1*),对于第一个字符来说,它的选择是有n中,而第二个字符就只有n-1种了,依次类推,最后一个字符只有一种选择,可以选择递归来实现,代码如下。
public ArrayList<String> firstPermutation(String str) {
ArrayList<String> arrayList = new ArrayList<>();
if (null == str || str.length() < 1) {
return arrayList;
}
messageStr(arrayList, 0, str.toCharArray());
return arrayList;
}
public void messageStr(ArrayList<String> arrayList, int start, char[] chars) {
//说明是最后一个字符了
if (start == chars.length - 1) {
String s = String.valueOf(chars);
if (!arrayList.contains(s)) {
arrayList.add(s);
}
} else {
for (int i = start; i < chars.length; i++) {
swap(chars, i, start);
messageStr(arrayList, start+1, chars);
//交换回位置,为了确保字符顺序不被改变
swap(chars, i, start);
}
}
}
private void swap(char[] char s, int i, int j) {
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
第二种解法,直接将所有情况列举出来,比如a,就只有一种情况,ab则有两种情况,ab,ba,如果此时再加一个c进来,变成abc,这个c可以放ab的前面,可以放ab的中间,也可以放ab的后面,依次类推,我们遍历所有情况即可,最后对list去个重即可,代码如下
public ArrayList<String> secondPermutation(String str) {
ArrayList<String> arrayList = new ArrayList<>();
if (null == str || str.length() < 1) {
return arrayList;
}
//将第一个数字放入集合李
arrayList.add(str.charAt(0)+"");
for(int i = 1; i < str.length(); i++){
ArrayList<String> resList = new ArrayList<>();
char c = str.charAt(i);
for (String s : arrayList) {
//放s前面
String result = c + s;
resList.add(result);
//放s后面
result = s + c;
resList.add(result);
// 加在中间
for (int j = 1; j < s.length(); j++) {
result = s.substring(0, j) + c + s.substring(j);
resList.add(result);
}
}
arrayList = resList;
}
return (ArrayList<String>) arrayList.stream().distinct().collect(Collectors.toList());
}