动态规划-字符串的全排列-JZ27

描述

输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述：

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

示例1

输入： “ab”

返回值： [“ab”,“ba”]

说明： 返回[“ba”,“ab”]也是正确的

示例2

输入： “aab”

返回值： [“aab”,“aba”,“baa”]

思路

针对排列问题，就是做选择的过程，我们需要进行n次选择，每次需要记录选择的数据且不能重复选择，具体过程如下：

1.遍历字符串中的字符，选择一个下标未加入过的字符（因为有重复不能比较字符值）加入记录中；

2.重复1过程，直到字符串中的字符都加入到了记录中；

3.撤销上一次的选择，选择上一次选择的下一个字符，并重复1,2；

4.直到上一次选择的下一个字符为空，选择过程结束。

在求排列的代码实现中，常使用回溯的方式，实现上述过程的回溯框架如下：

// 排列结果
List<String> res;
// 字符数组chars，选择数据记录memo
backtrack(char[] chars, StringBuilder memo){
    if(memo.length() == chars.length && res中没有memeo){
         /将memo加入到res中，并返回
    }
    for(int i=0;i<chars.length;i++){  
        if(memo中有chars[i]字符) 跳过；
        memo.append(chars[i]);// 做选择，memo加入此字符
        backtrack(chars, memo); //回溯
        memo.deleteCharAt(memo.length()-1); // 撤销选择，返回上一次选择
    }
}
           

时间复杂度：O(n!)，其中 n 为给定字符串的长度。这些字符的全部排列有 O(n!) 个。

空间复杂度：O(n)。我们需要 O(n) 的栈空间进行回溯。

代码

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] chars = str.toCharArray();
        // 使用treeSet来保证结果是按照字典序排列的，不用事先排序
        TreeSet<String> treeSet = new TreeSet<>();
        perm(chars, 0, treeSet);
        result.addAll(treeSet);
        return result;
    }
    private void perm(char[] chars, int begin, TreeSet<String> treeSet) {
        if (chars == null || chars.length == 0 || begin > chars.length-1) {
            return;
        }
        if (begin == chars.length-1) {
            treeSet.add(String.valueOf(chars));
            return;
        }
        for (int i = begin; i < chars.length; i++) {
            swap(chars, begin, i);
            perm(chars, begin+1, treeSet);
            swap(chars, begin, i);
        }
    }
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}