算法题:输入一个不存在重复字符的字符串,打印出字符串中字符的全部排列组合。
代码实现:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::swap
void permute(std::string str, int left, int right) {
if (left == right) {
std::cout << str << std::endl;
} else {
for (int i = left; i <= right; i++) {
// 交换字符
std::swap(str[left], str[i]);
// 递归调用,生成剩余字符的排列
permute(str, left + 1, right);
// 交换回来,以便下一次的排列
std::swap(str[left], str[i]);
}
}
}
int main() {
std::string input = "123";
int n = input.size();
permute(input, 0, n - 1);
return 0;
}
解释:
-
permute
函数:- 这个递归函数生成所有字符的排列组合。
- 参数
str
是输入字符串,left
是当前正在考虑的字符位置,right
是字符串的最后一个字符位置。
-
递归基准情况:
- 当
left == right
时,表示所有字符都已经排列完毕,直接打印当前的排列。
- 当
-
递归过程:
- 通过交换
str[left]
和str[i]
,不同字符被置于当前考虑的位置。 - 然后,递归调用
permute
函数来生成剩余字符的排列组合。 - 最后,交换字符回到原始位置,以便继续生成其他可能的排列。
- 通过交换
-
主函数
main
:- 调用
permute
函数,从字符串的第一个字符开始生成排列。
- 调用
复杂度分析:
- 时间复杂度:生成所有排列组合的时间复杂度为 O(n!),其中 n 是字符串的长度。每个排列都需要 O(n) 的时间来生成和打印。
- 空间复杂度:递归调用栈的空间复杂度为 O(n)。