给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z',而且给定的字符串中的字母已经按照从小到大的顺序排列。
时间: 2023-06-01 12:01:56 浏览: 135
算法思路:
我们可以使用递归的思想来解决这个问题。首先,我们考虑只有两个元素的情况。我们可以把这两个元素交换位置,得到两个不同的排列,然后再交换回来,得到另外两个不同的排列。对于 n 个元素,我们可以先将第一个元素和其他元素依次交换,然后对剩余元素进行全排列。这样可以把问题转化为一个规模更小的问题。具体来说,我们可以固定第一个元素,对剩余元素进行全排列;然后再将第一个元素和其他元素交换,对剩余元素进行全排列,以此类推。
算法实现:
我们可以定义一个递归函数 permute,用来求出给定字符串的所有全排列。该函数接受三个参数,分别为字符串 s、当前访问到的位置 pos,以及存储结果的列表 res。初始时 pos=0,res=[]。在函数 permute 中,我们首先判断 pos 是否等于字符串 s 的长度,如果是,说明已经访问到字符串的末尾,此时将当前排列加入到结果列表 res 中;否则,我们对剩余的元素进行全排列,然后将第一个元素和其他元素依次交换,对剩余元素进行全排列。具体的实现如下:
C++ 代码
class Solution {
public:
vector<string> permutation(string s) {
vector<string> res;
permute(s, 0, res);
return res;
}
void permute(string s, int pos, vector<string>& res) {
if (pos == s.size()) {
res.push_back(s);
return;
}
for (int i = pos; i < s.size(); i++) {
if (i != pos && s[i] == s[pos]) continue;
swap(s[i], s[pos]);
permute(s, pos + 1, res);
}
}
};
Python 代码
class Solution:
def permutation(self, s: str) -> List[str]:
res = []
def permute(s, pos):
if pos == len(s):
res.append(''.join(s))
return
for i in range(pos, len(s)):
if i != pos and s[i] == s[pos]:
continue
s[i], s[pos] = s[pos], s[i]
permute(s, pos + 1)
s[i], s[pos] = s[pos], s[i]
permute(list(s), 0)
return res
复杂度分析:
时间复杂度:O(n*n!),其中 n 是字符串 s 的长度。全排列的个数是 n!,对于每个排列,我们需要 O(n) 的时间来复制字符串,因此总时间复杂度是 O(n*n!)。
空间复杂度:O(n*n!),其中 n 是字符串 s 的长度。空间复杂度取决于结果列表 res 的大小,结果列表中最多包含 n! 个字符串,每个字符串的长度是 n,因此总空间复杂度是 O(n*n!)。