package com.leetcode;

import java.util.ArrayList;

public class Permutation {
	
	public static void main(String[] args) {
		ArrayList<String> res = perms2("abc");
		System.out.println(res);
	}
	
	//法一：
	public static ArrayList<String> perms1(String s){
		ArrayList<String> res = new ArrayList<String>();
		if(s == null)
			return null;
		if(s.isEmpty()){
			res.add("");
			return res;
		}
		for(int i = 0; i < s.length(); i++){
			char c = s.charAt(i);
			String start = s.substring(0, i);
			String end = s.substring(i + 1);
			ArrayList<String> words = perms1(start + end);
			for(String word : words){
				String newStr = c + word;
				res.add(newStr);
			}
		}
		return res;
	}
	
	//法二：
	public static ArrayList<String> perms2(String s){
		ArrayList<String> res = new ArrayList<String>();
		if(s == null)
			return null;
		if(s.isEmpty()){
			res.add("");
			return res;
		}
		char c = s.charAt(0);
		String reminder = s.substring(1);
		ArrayList<String> words = perms2(reminder);
		for(String word : words){
			for(int i = 0; i <= word.length(); i++){
				String newStr = insertCharAt(word, c, i);
				res.add(newStr);
			}
		}
		return res;
	}
	
	public static String insertCharAt(String s, char c, int i){
		String start = s.substring(0, i);
		String end = s.substring(i);
		return start + c + end;
	}
}

Java实现字符串的全排列