9.9递归和动态规划（五）——确定某字符串的全部排列组合

/**
 * 功能：确定某字符串的全部排列组合。

 */

注意：不考虑反复字符。若考虑反复字符，仅仅需在增加permulations时去掉反复的字符串就可以。

	/**
	 * 思路：元素由少到多，将新的元素塞进全部字符串中间的随意可能位置。
	 * @param str
	 * @return
	 */
	public static ArrayList<String> getPerms(String str){
		
		if(str==null)
			return null;
		
		ArrayList<String> permutations=new ArrayList<String>();
		if(str.length()==0){
			permutations.add("");
			return permutations;
		}
		
		char first=str.charAt(0);
		String remainder=str.substring(1);
		ArrayList<String> words=getPerms(remainder);
		for(String word:words){
			for(int i=0;i<=word.length();i++){
				String s=insertCharAt(word, first, i);
				permutations.add(s);
			}
		}
		
		
		
		return permutations;
	}
	
	public static String insertCharAt(String word,char c,int i){
		String start=word.substring(0, i);
		String end=word.substring(i);
		return start+c+end;
	}