输出字符串的全排列

问题描述

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

思路分析

回想字符串的模式匹配思想，我们可以将该字符串分成两部分，一部分是第一个字符串，第二部分是剩余的字符，然后保持第一个字符不变，从剩余字符遍历，同时交换遍历的位置，很显然这是一个递归的过程，最后在回溯，交换第一个字符和剩余字符的位置，依次类推

码上有戏

public class StringSort {
	
	public ArrayList<String> permitution(String str){
		ArrayList<String> list=new ArrayList<String>();
		 if(str==null||str.length()<0)
			 return list;
		 list=permitution(list,str.toCharArray(),0,str.length());
		  Collections.sort(list);
		  return list;
	}
	
	private ArrayList<String> permitution(ArrayList<String> list,char[] str,int begin,int length)
	{
		if(begin==length-1)
		{
			if(!list.contains(str))
				list.add(String.valueOf(str));
		}
		else{
			for(int i=begin;i<length;i++){
				if(i==begin||str[i]!=str[begin]){
					swap(str,begin,i);
					permitution(list,str,begin+1,length);
					swap(str,begin,i);
				}
			}
		}
		return list;
	}
	public void swap(char[] str,int begin,int i){
		char temp=str[i];
		str[i]=str[begin];
		str[begin]=temp;
	}
	
	public static void main(String[] args) {
		ArrayList<String> list=new StringSort().permitution("abcc");
         for(String s:list){
        	 System.out.print(s+" ");
         }
	}

}