文章482
标签257
分类63

算法:字符串的排列


字符串的排列

字符串的排列

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

例如输入字符串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;
    }
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/1996/07/27/算法-字符串的排列/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可