剑指 Offer 38. 字符串的排列

题目地址(38. 字符串的排列)

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8

前置知识

公司

• 暂无

思路

这题和全排列完全一样 只是用string换了int
第二次做还是不会

关键点

代码

• 语言支持：Java

Java Code:

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    //返回值
    ArrayList<String> res;
    //单个满足返回值要求的路径
    StringBuilder path;
    //判断每个char是否被使用过
    boolean[] used;
    public String[] permutation(String s) {
        res = new ArrayList<>();
        path = new StringBuilder();
        char[] chars = s.toCharArray();
        used = new boolean[chars.length];
        //排序 目的是让相同的字符排在一起
        Arrays.sort(chars);
        dfs(chars, 0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(char[] chars, int depth) {
        //深度等于字符串的长度说明遍历到叶子节点了
        if (depth == chars.length) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            // 防止越界   当前字符和前面的字符相同 并且是在同一层
            //used[i]为true 说明是在同一树枝上有相同的数字
            if (i > 0 && chars[i - 1] == chars[i] && !used[i - 1]) {
                continue;
            }
            //判断树枝上有没有取过该值 为true表示取过
            if (!used[i] ) {
                //递归下一层把当前字符加入 并使used为true表示取过该值 在下一层的同层for中不会重复的取当前值
                path.append(chars[i]);
                used[i] = true;
                dfs(chars, depth + 1);
                //回溯
                used[i]=false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=TxSDu)
• 空间复杂度：#card=math&code=O%28n%29&id=i7d42)