08.08. Permutation II
Description
Write a method to compute all permutations of a string whose charac ters are not necessarily unique. The list of permutations should not have duplicates.
Example1:
Input: S = "qqe" Output: ["eqq","qeq","qqe"]
Example2:
Input: S = "ab" Output: ["ab", "ba"]
Note:
- All characters are English letters.
1 <= S.length <= 9
Solutions
Solution 1: Sorting + Backtracking
We can first sort the string by characters, which allows us to put duplicate characters together and makes it easier for us to remove duplicates.
Then, we design a function $dfs(i)$, which means that we need to fill in the character at the $i$-th position. The specific implementation of the function is as follows:
- If $i = n$, it means that we have finished filling in, add the current permutation to the answer array, and then return.
- Otherwise, we enumerate the character $s[j]$ at the $i$-th position, where the range of $j$ is $[0, n - 1]$. We need to ensure that $s[j]$ has not been used and is different from the previously enumerated characters, so as to ensure that the current permutation is not repeated. If the conditions are met, we can fill in $s[j]$, and continue to recursively fill in the next position, that is, call $dfs(i + 1)$. After the recursive call ends, we need to mark $s[j]$ as unused for later enumeration.
In the main function, we first sort the string, then call $dfs(0)$, that is, start filling from the $0$-th position, and finally return the answer array.
The time complexity is $O(n \times n!)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$. $n!$ enumerations need to be performed, and each enumeration requires $O(n)$ time to determine whether it is repeated. In addition, we need a marker array to mark whether each position has been used, so the space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|