字符串的排列

题目描述

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

解题思路

• 基于回溯法

代码

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> ret = new ArrayList<>();
        if (str == null || str.length() == 0)
            return ret;
        helper(str.toCharArray(), 0, ret);
        Collections.sort(ret);
        return ret;
    }
    
    private void helper(char[] cs, int swapIndex, ArrayList<String> ret) {
        if (swapIndex == cs.length-1) {
            String val = String.valueOf(cs);
            if (!ret.contains(val))
                ret.add(val);
        } else {
            for (int j = swapIndex; j < cs.length; j++) {
                swap(cs, swapIndex, j);
                helper(cs,swapIndex+1, ret);
                swap(cs, swapIndex, j);
            }
        }
    }
    
    private void swap(char[] cs, int pre, int post) {
        char tmp = cs[pre];
        cs[pre] = cs[post];
        cs[post] = tmp;
    }
}