无重复字符串的排列组合
难度:
标签:
题目描述
Write a method to compute all permutations of a string of unique characters.
Example1:
Input: S = "qwe" Output: ["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
Example2:
Input: S = "ab" Output: ["ab", "ba"]
Note:
- All charaters are English letters.
1 <= S.length <= 9
代码结果
运行时间: 43 ms, 内存: 21.7 MB
/*
* 思路：
* 使用Java Stream API和递归来生成字符串的所有排列组合。将字符串拆分成字符数组，
* 然后通过流操作递归地生成所有排列。
*/
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StreamPermutations {
public static List<String> getPermutations(String S) {
if (S.isEmpty()) {
return List.of("");
}
return IntStream.range(0, S.length())
.mapToObj(i -> {
String remaining = S.substring(0, i) + S.substring(i + 1);
return getPermutations(remaining).stream()
.map(p -> S.charAt(i) + p)
.collect(Collectors.toList());
})
.flatMap(List::stream)
.collect(Collectors.toList());
}
public static void main(String[] args) {
System.out.println(getPermutations("qwe")); // [qwe, qew, wqe, weq, ewq, eqw]
}
}解释
方法:
这个题解使用了回溯算法来生成字符串的所有排列。首先，将字符串转化为字符列表，然后通过递归的深度优先搜索（DFS）方法，通过不断交换字符位置来探索所有可能的排列。具体而言，对于每个递归层，算法通过遍历从当前位置到字符串末尾的所有字符，并与当前位置的字符进行交换，来生成新的排列。交换后，算法递归到下一个位置，继续进行字符交换直到到达字符串的末尾，此时记录一个完整的排列。随后，通过回溯（即再次交换字符）恢复原字符串的顺序，以便进行后续的排列生成。
时间复杂度:
O(n*n!)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归方法`dfs`中，为什么要在递归到字符串最后一个字符时直接将排列结果添加到结果列表中，而不是继续交换？
▷🦆
回溯算法中的交换步骤`s[i], s[x] = s[x], s[i]`进行了两次，请解释为什么需要在递归调用后再次交换回来？
▷🦆
如何保证生成的排列中不会有重复，尽管字符串中的字符都是独一无二的？
▷