Skip to content

08.07. Permutation I

Description

Write a method to compute all permutations of a string of unique characters.

Example1:


 Input: S = "qwe"

 Output: ["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

Example2:


 Input: S = "ab"

 Output: ["ab", "ba"]

Note:

  1. All characters are English letters.
  2. 1 <= S.length <= 9

Solutions

Solution 1: DFS (Backtracking)

We design a function $dfs(i)$ to represent that the first $i$ positions have been filled, and now the $i+1$ position needs to be filled. We enumerate all possible characters, if this character has not been filled, we fill in this character, and then continue to fill the next position until all positions are filled.

The time complexity is $O(n \times n!)$, where $n$ is the length of the string. There are $n!$ permutations in total, and each permutation takes $O(n)$ time to construct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def permutation(self, S: str) -> List[str]:
        def dfs(i: int):
            if i == n:
                ans.append("".join(t))
                return
            for j, c in enumerate(S):
                if vis[j]:
                    continue