算法:字符串的排列

字符串的排列

字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。

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

分析

本质上是求组成字符串的字符能组成的全排列;

使用回溯法:

通过交换字符串对应的位置进行字符串构建, 而[start, len - 1]是还未使用的字符

最后的结果放在TreeMap中, 保证结果是按字典顺序排列的;

代码

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        TreeSet<String> res = new TreeSet<>();
        if (str == null || str.length() == 0) return new ArrayList<>();
        helper(str.toCharArray(), 0, res);
        return new ArrayList<>(res);
    }

    private void helper(char[] arr, int start, TreeSet<String> res) {
        if (start == arr.length - 1) {
            res.add(new String(arr));
            return;
        }

        for (int i= start; i < arr.length; ++i) {
            swap(arr, start, i);
            helper(arr, start + 1, res);
            swap(arr, start, i);
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}