剑指 Offer 38. 字符串的排列

Offer_38

题目描述

解题思路

1. 可以使用递归实现全排列，每次都确定一个数的位置，当所有位置的数都确定后即表示一个排列。
2. 但是考虑到本题需要排除重复的排列，所以可以递归时判断同一个字符是否出现在某个位置多次，如果出现多次则跳过。

java代码

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/2/5 22:45

 */

import java.util.LinkedList;

import java.util.List;

import java.util.TreeSet;

/**

 * 题目详情：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 * 解题思路：可以使用递归实现全排列，每次都确定一个数的位置，当所有位置的数都确定后即表示一个排列。但是考虑到本题需要排除重复的排列，

 * 所以可以递归时判断同一个字符是否出现在某个位置多次，如果出现多次则跳过。

 */

public class Offer_38 {

    List<String> result = new LinkedList<>();

    char[] chs;

    public String[] permutation(String s) {

        chs = s.toCharArray();//将字符串s转换为字符数组

        dfs(0);

        return result.toArray(new String[result.size()]);

    }

    void dfs(int num){

        if(num == chs.length - 1){

            result.add(String.valueOf(chs));

            return;

        }

        TreeSet<Character> treeSet = new TreeSet<>();

        for(int i = num; i<chs.length; i++){

            if(treeSet.contains(chs[i])){

                continue;

            }

            treeSet.add(chs[i]);

            swap(i, num);

            dfs(num + 1);

            swap(i, num);

        }

    }

    void swap(int a, int b){

        char temp = chs[b];

        chs[b] = chs[a];

        chs[a] = temp;

    }

}