题目描述

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

输入描述:

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

解题思路

首先固定第一位，然后递归处理后面的位，每次递归中与当前位后面的每一位交换，知道处理到最后一位。由于要按照字母顺序输出，需要对列表排序。

实现

import java.util.ArrayList;import java.util.Collections;public class Solution {    public ArrayList
    
      Permutation(String str) {        ArrayList
     
       list = new ArrayList<>();        if (str == null || str.length() <= 0) return list;        char[] chars = str.toCharArray();        recursion(chars, list, 0);        Collections.sort(list);        return list;    }    private void recursion(char[] chars, ArrayList
      
        list, int i) {        if (i == chars.length) {            list.add(String.valueOf(chars));        }        for (int j = i; j < chars.length; j++){            if (i !=j && chars[i] == chars[j]) continue;            swap(chars, i, j);            recursion(chars, list, i+1);            swap(chars, i, j);        }    }    private void swap(char[] chars, int i, int j) {        char tmp = chars[i];        chars[i] = chars[j];        chars[j] = tmp;    }}