剑指 Offer 38. 字符串的排列（Medium）（JAVA）每日一题

本文主要是介绍剑指 Offer 38. 字符串的排列（Medium）（JAVA）每日一题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

剑指 Offer 38. 字符串的排列（Medium）（JAVA）

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

题目描述：

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

示例:

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

限制：

1 <= s 的长度 <= 8

解题方法

要找出字符串的排列，关键是字符串里面的字符可能是重复的，该如何去重：现对字符排序，再让相同的字符只能运算一次

1. 对字符串的所有字符进行排序，然后把所有字符放到一个 list 里面
2. 采用递归的形式，把字符串里面的字符按序取出来，组成一个字符串
3. 为了不出现重复的字符串，如果当前字符和前一个字符相同，说明有过这个排序了，直接跳过即可

class Solution {
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            list.add(chars[i]);
        }
        char[] temp = new char[chars.length];
        List<String> res = new ArrayList<>();
        pH(list, temp, res);
        String[] strs = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            strs[i] = res.get(i);
        }
        return strs;
    }
    
    public void pH(List<Character> list, char[] temp, List<String> res) {
        if (list.size() == 0) {
            res.add(String.valueOf(temp));
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            if (i > 0 && list.get(i) == list.get(i - 1)) continue;
            temp[temp.length - list.size()] = list.get(i);
            char tempChar = list.remove(i);
            pH(list, temp, res);
            list.add(i, tempChar);
        }
    }
    
}

执行耗时:18 ms,击败了48.66% 的Java用户
内存消耗:42.7 MB,击败了80.59% 的Java用户

这篇关于剑指 Offer 38. 字符串的排列（Medium）（JAVA）每日一题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！