用c++写给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有‘a’<‘b’<...<‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}

void Permutation(char *str, int begin, int end) {
if (begin == end) {
printf("%s\n", str);
return;
}
int i;
for (i = begin; i <= end; i++) {
swap(str + begin, str + i);
Permutation(str, begin + 1, end);
swap(str + begin, str + i);
}
}

int main() {
char str[27];
scanf("%s", str);
int len = strlen(str);
Permutation(str, 0, len - 1);
return 0;
}

相关问题

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

算法思路：

我们可以使用递归的思想来解决这个问题。首先，我们考虑只有两个元素的情况。我们可以把这两个元素交换位置，得到两个不同的排列，然后再交换回来，得到另外两个不同的排列。对于 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!)。

C++给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出no。

可以使用哈希表来解决这个问题。遍历一遍字符串，将每个字符出现的次数记录在哈希表中。然后再遍历一遍字符串，找到第一个出现次数为1的字符即可。

C++代码如下：

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    string s;
    cin >> s;
    unordered_map<char, int> count;
    for (char c : s) {
        count[c]++;
    }
    for (char c : s) {
        if (count[c] == 1) {
            cout << c << endl;
            return 0;
        }
    }
    cout << "no" << endl;
    return 0;
}

时间复杂度为 O(n)，空间复杂度为 O(字符集大小)。