剑指 Offer 38. 字符串的排列

本问题对应的 leetcode 原文链接:剑指 Offer 38. 字符串的排列
对应配套打卡:【回溯专题】剑指 Offer 38. 字符串的排列

问题描述

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

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

限制:

1 <= s 的长度 <= 8

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    List<Character> path;
    List<String> res;
    boolean[] visited;
    public String[] permutation(String s) {
        this.path = new ArrayList<>();
        this.res = new ArrayList<>();
        this.visited = new boolean[s.length()];

        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, 0);

        String[] ss = new String[res.size()];
        for(int i = 0; i < res.size(); i++){
            ss[i] = res.get(i);
        }

        return ss;

    }
    // 时间复杂度:O(n*n!) 空间:N,N,递归调用最大深度也是 N,3n,O(n)
    void dfs(char[] arr, int k){
        if(arr.length == k){
           res.add(listToString(path));
           return;
        }

        //进行N叉树搜索
        for(int i = 0; i < arr.length; i++){
            // 剪枝 aab
            if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
                continue;
            }
            if(visited[i] == false){
                // 递归访问
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr, k + 1);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }

    String listToString(List<Character> list){
        StringBuilder b = new StringBuilder();
        for(int i = 0; i < list.size(); i++){
            b.append(list.get(i));
        }

        return b.toString();
    }
}

时间复杂度:O(n!n)
空间复杂度:O(n^2)

发表回复

后才能评论