通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 38. 字符串的排列

261人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/913

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 38. 字符串的排列

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

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

示例:

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

限制:

1 <= s 的长度 <= 8


难度:中等;标签:回溯算法;编程语言:JAVA


 其它方法

class Solution {
    // 题解中的解法:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation2(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c)); // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复,因此剪枝
            set.add(c[i]);
            swap(i, x); // 交换,将 c[i] 固定在第 x 位 
            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x); // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

做过类似的,忘了,题解中的方法,思路很清晰,把每个不同的数分别放在第一位,第二位,第。。。。,如果没有重复的数,第一位有n种情况,第二位有n-1种情况,。。。。,因为可能有重复,所以用set去重,swap的意思是第i位原来的数到后面,构成其它的情况,具体可以看题解方法


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告