从今天起重新做人，打算用python刷题。因为java用得太少，感觉语法和类型没有肌肉记忆总会忘。py经常用，忘的概率会小一点点。

主要思路：

  • 递归，DFS，剪枝。
  • 递归终止：当DFS进行到len(s)-1时说明当前分支深度搜索已经完成，返回一个字符串。
  • 递推：当DFS进行到第x位时，依次递推将x位和range(x, len(s)-1)位置的第i位交换，然后进入下一层递归dfs(x+1)，递归结束返回当前一层后将交换的两位还原，全当无事发生。
  • 剪枝：例如abbcc的输入字符串可能会导致两位交换后的DFS过程不能说是毫无差别，只能说是完全一致。这种情况在每一层递归的时候新建一个hashset保存本层已经固定处理过的字符，而在递推的过程中就可以对已经固定过的字符进行剪枝操作。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def permutation(self, s: str) -> List[str]:
    res = []
    s_ = list(s)
    def recur(x):
        if x == len(s_) - 1:
            res.append(''.join(s_))
            return
        dic = set()
        for i in range(x, len(s_)):
            if s_[i] in dic:
                continue
            dic.add(s_[i])
            s_[x], s_[i] = s_[i], s_[x]
            recur(x + 1)
            s_[x], s_[i] = s_[i], s_[x]
    recur(0)
    return res