剑指offer-字符串的排列

题目描述

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

输入描述:

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

思路

对于无重复值的情况： 固定第一个字符，递归取得首位后面的各种字符串组合；

再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； 递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。 假如有重复值呢？

可以做一个判断，判断输出的list中是否已经有了这串字符，有的话就不加进去。

import java.util.List;
import java.util.Collections;

import java.util.ArrayList;
public class Solution {

	public static void main(String[] args) {
	    Solution p = new Solution();
	    System.out.println(p.Permutation("abc").toString());// 转换为字符串输出
	}

	public ArrayList<String> Permutation(String str) {
	    List<String> res = new ArrayList<>();
	    if (str != null && str.length() > 0) {
	        PermutationHelper(str.toCharArray(), 0, res); // 将str字符串转换为字符数组
	        Collections.sort(res); // 按字母顺序排序
	    }
	    return (ArrayList)res;
	}

	public void PermutationHelper(char[] cs, int i, List<String> list) {
	    if (i == cs.length - 1) {
	        String val = String.valueOf(cs);
	        if (!list.contains(val)) // 没有重复则加入list数组中
	            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[i];
	    cs[i] = cs[j];
	    cs[j] = temp;
	}
}