剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列

问题

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

分析

  1. 定位：通过选择，定住左面m位字符，再 考虑后面n-m位字符；（分治）
  2. 定住的位数，可以通过visited记录；（剪枝）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
'''一般想法'''
class Solution:
    def permutation(self, s: str) -> List[str]:
        def backtrack(s, path):
            if not s: self.res.append(path)
            visited = set()
            for i in range(len(s)):
                if s[i] in visited: continue
                visited.add(s[i])
                backtrack(s[:i]+s[i+1:], path + s[i])
        self.res = []
        n = len(s)
        backtrack(s, "")
        return self.res

通过交换操作，优化时间复杂度。

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