剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制：
1 <= s 的长度 <= 8

解题思路

可以把s看做森林（a，b，c开头的三棵树），然后使用dfs+剪枝（剪掉重复的路径）来做这个题，剪完以后的路径list就是想要的结果。

• dfs：使用递归+visited数组来进行深度遍历。在遍历之前，visited数组为[False, False, False]。每当我们遍历到位置i，就把visited[i]置为True，并在此处递归执行dfs()。在此dfs()执行完后，将此visited[i]重新置为False，解放此字符的访问权限，使其像是森林一样进行前序遍历。"abc"的dfs顺序为['abc', 'acb', 'bac', 'bca', 'cab', 'cba']。
• 剪枝：剪枝的目的是防止输入为"aab"之类含有重复字符的字符串。此类字符串如果不使用剪枝，会造成["aab","aba","aab","aba","baa","baa"]这种含有重复字符串的结果，正确的结果是将其剪成["aba","aab","baa"]。这里可以用python的set来剪掉，既可以将list转为set，也可以直接用set.add()。

注意，python的list的添加是append，而set的添加是add。
字符串末尾追加字符的方式是str += char，删除字符的方式是str = str[:-1]。

解题代码

class Solution:
    def permutation(self, s: str) -> list[str]:
        result = set()
        visited = [False for _ in range(len(s))]

        def dfs(path: str):
            # 如果已经遍历到字符串的最后一个字符，就可以把得到的遍历出来的字符串加进结果数组了
            if len(path) == len(s):
                result.add(path)
                return
            for i in range(len(s)):
                if visited[i] is False:
                    path += s[i]
                    visited[i] = True
                    dfs(path)
                    visited[i] = False # 例如在第一遍产生abc之后，回到这里解放b，才能把b换成之前解放的c，并在c后面加上解放了的b。（回溯）
                    path = path[:-1] # 都解放了b，就从队伍里面清理掉，之后才能新加c
        dfs("")
        return list(result)

执行结果

执行用时: 280 ms
内存消耗: 24.8 MB