9.5 Write a method to compute all permutations of a string.
LeetCode上的原题，请参加我之前的博客Permutations 全排列和Permutations II 全排列之二。
解法一：
class Solution {
public:
vector<string> getPerms(string &s) {
vector<string> res;
getPermsDFS(s, , res);
return res;
}
void getPermsDFS(string &s, int level, vector<string> &res) {
if (level == s.size()) res.push_back(s);
else {
for (int i = level; i < s.size(); ++i) {
swap(s[level], s[i]);
getPermsDFS(s, level + ,res);
swap(s[level], s[i]);
}
}
}
};
解法二：
class Solution {
public:
vector<string> getPerms(string s) {
vector<string> res;
vector<bool> visited(s.size(), false);
getPermsDFS(s, , visited, "", res);
return res;
}
void getPermsDFS(string s, int level, vector<bool> &visited, string out, vector<string> &res) {
if (level == s.size()) res.push_back(out);
else {
for (int i = ; i < s.size(); ++i) {
if (!visited[i]) {
visited[i] = true;
out.push_back(s[i]);
getPermsDFS(s, level + , visited, out , res);
out.pop_back();
visited[i] = false;
}
}
}
}
};
解法三：
class Solution {
public:
vector<string> getPerms(string s) {
if (s.empty()) return vector<string>(, "");
vector<string> res;
char first = s[];
string remainder = s.substr();
vector<string> words = getPerms(remainder);
for (auto &a : words) {
for (int i = ; i <= a.size(); ++i) {
string out = insertCharAt(a, first, i);
res.push_back(out);
}
}
return res;
}
string insertCharAt(string s, char c, int i) {
string start = s.substr(, i);
string end = s.substr(i);
return start + c + end;
}
};