题目
题目描述
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例
输入: s = “abc”
输出: [“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
题解
(引用Krahets)
回溯DFS
深度优先搜索，先固定高位，后固定低位。当字符重复时剪枝。
每个当前位置新建一个set，用于存储字符序列并去除重复字符。
时间复杂度: O(n!)，共有 n(n-1)…21 种方案;
空间复杂度: O($n^2$)，DFS递归深度为n，递归辅助set累计存储 $n+(n-1)+..+2+1=(n+1)n/2$，即占用O($n^2$)额外空间;
class Solution:
def permutation(self, s: str) -> List[str]:
path, res = list(s), []
def dfs(loc):
if loc == len(path) - 1:
res.append(''.join(path))
return
exist = set()
for i in range(loc, len(path)):
if path[i] in exist:
continue
exist.add(path[i])
path[i], path[loc] = path[loc], path[i]
dfs(loc+1)
path[i], path[loc] = path[loc], path[i]
dfs(0)
return res
|
