题解 | JZ38 字符串的排列
因为本题的答案不看顺序，所以，也不用对初始数据进行预处理。
本题最核心的函数就是dfs，关键看里面是怎么操作的。
因为要N!把所有情况都遍历一遍，所以我们想到要配合一个done[]数组，来记录我们当前已经把哪些字符算进去了，这样好做到不重复。同时，我们还需要一个num变量记录一下当前已经加入了多少个字符进去。加num的目的是，为了让dfs()函数知道在哪里退出出来。
在dfs()函数里，我们用for循环暴力遍历每一个情况，并用done数组记录每一个字符是否在当前统计中添加进去，这样能够保证不重复不遗漏。
这里，我们还发现了像aa这样的字符串，它最终返回的结果是aa而不是aa, aa。也就是相同的字符串结果只统计一遍，所以我们需要用一个集合来记录重复值。
class Solution {
public:
vector<string> ans;
string tmp;
set<string> se;
vector<string> Permutation(string str) {
int len = str.length();
bool done[len];
memset(done, false, sizeof(done));
dfs(done, 0, len, str);
return ans;
}
void dfs(bool done[], int num, int len, string str) {
if (num == len) {
if (se.find(tmp) == se.end()) {
ans.push_back(tmp);
se.insert(tmp);
}
return;
}
for (int i = 0; i < len; i++) {
if (!done[i]) {
tmp += str[i];
done[i] = true;
dfs(done, num+1, len, str);
tmp.erase(tmp.end()-1);
done[i] = false;
}
}
}
};
# -*- coding:utf-8 -*-
class Solution:
ans = []
dic = {}
tmp = []
def Permutation(self, ss):
# write code here
self.done = [False] * len(ss)
self.dfs(ss, 0, len(ss))
return self.ans
def dfs(self, ss, num, ll):
if num == ll:
if not self.dic.get(''.join(self.tmp)):
self.ans.append(''.join(self.tmp))
self.dic[''.join(self.tmp)] = 1
for i in range(ll):
if not self.done[i]:
self.done[i] = True
self.tmp.append(ss[i])
self.dfs(ss, num+1, ll)
self.done[i] = False
self.tmp.pop()
腾讯HR面1953人在聊
查看5道真题和解析