【剑指offer】字符串的排列

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路 把这个问题分解为两步，第一步，先把第一个字固定，求字符串中剩下的字符的全排列。剩下字符的全排列也可以通过先把剩下的字符分为第一个字符和后面字符的全排列，因此很容易想到用递归。

代码

import java.util.*; public class Solution{ public ArrayList Permutation(String str) { ArrayList res = new ArrayList(); if (str != null && str.length() > 0) { PermutationHelper(str.toCharArray(), 0, res); Collections.sort(res); } return res; } public void PermutationHelper(char[] cs, int i, ArrayList list) { if(i == cs.length - 1) { String val = String.valueOf(cs); if (!list.contains(val)) list.add(val); } else { for(int j = i; j < cs.length; ++j) { swap(cs, i, j);//交换两个字符// PermutationHelper(cs, i + 1, list);//对后面的字符全排列// swap(cs, i, j);//把交换后的字符串复原// } } } public void swap(char[] cs, int i, int j){ char temp = cs[j]; cs[j] = cs[i]; cs[i] = temp; } }