剑指offer1：字符串的排列

题目描述

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

输入描述:

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

解答

package digui;

import java.util.ArrayList;
import java.util.Comparator;

public class Demo1_Solution {
	public static void main(String[] args) {
		String str = "abc";
		Demo1_Solution ds = new Demo1_Solution();
		ArrayList<String> list = ds.Permutation(str);
		
		System.out.println(list);
	}
	
	public ArrayList<String> Permutation(String str) {
		char[] c = str.toCharArray();
		
		ArrayList<String> list = new ArrayList<>();
		
		if (c.length == 0) {
			return list;
		} else {
			demo_Permutation(list,c,0);
		}
		list.sort(new Comparator<String>(){

			@Override
			public int compare(String o1, String o2) {
				
				return o1.compareTo(o2);
			}
			
		});
		return list;
    }

	private void demo_Permutation(ArrayList<String> list,char[] c, int k) {
		if (k == c.length) {
			String str = String.valueOf(c);
			if (!list.contains(str)) {
				list.add(str);
			}
			
		} else {
			for (int i = k; i < c.length; i++ ) {
				swap(c,i,k);
				demo_Permutation(list,c,k+1);
				swap(c,i,k);
			}
		}
		
	}
	private void swap(char[] c, int i, int k) {
		char c1;
		c1 = c[i];
		c[i] = c[k];
		c[k] = c1;
		
	}
}

运行时间和所占用的内存