题目

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
image.png

思路

dfs

代码

  1. class Solution:
  2.     def permutation(self, s: str) -> List[str]:
  3.         c, res = list(s), []
  4.         def dfs(x):
  5.             if x == len(c) - 1:
  6.                 res.append(''.join(c)) # 添加排列方案
  7.                 return
  8.             dic = set()
  9.             for i in range(x, len(c)):
  10.                 if c[i] in dic:
  11.                     continue # 重复，因此剪枝
  12.                 dic.add(c[i])
  14.                 c[i], c[x] = c[x], c[i] # 交换，将 c[i] 固定在第 x 位
  15.                 dfs(x + 1) # 开启固定第 x + 1 位字符
  16.                 c[i], c[x] = c[x], c[i] # 恢复交换
  17.         dfs(0)
  18.         return res