题目地址: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
限制:
1 <= s 的长度 <= 8
要找出字符串的排列,关键是字符串里面的字符可能是重复的,该如何去重:现对字符排序,再让相同的字符只能运算一次
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用户