题目：输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
练习地址
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
参考答案
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
return result;
}
permutation(str.toCharArray(), 0, result);
// 对结果有序输出
Collections.sort(result);
return result;
}
private void permutation(char[] chars, int start, ArrayList<String> result) {
if (start == chars.length - 1) {
result.add(new String(chars));
} else {
for (int i = start; i < chars.length; i++) {
if (chars[i] != chars[start]) {
char temp = chars[i];
chars[i] = chars[start];
chars[start] = temp;
}
// 对重复的字母，例如"aa"，不会重复输出
if (i == start || chars[i] != chars[start]) {
permutation(chars, start + 1, result);
}
if (chars[i] != chars[start]) {
char temp = chars[i];
chars[i] = chars[start];
chars[start] = temp;
}
}
}
}
}
复杂度分析
- 时间复杂度：O(n!)。
- 空间复杂度：O(n)。
