难度: Medium
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:
输入：S = "qqe" 输出：["eqq","qeq","qqe"]
示例2:
输入：S = "ab" 输出：["ab", "ba"]
提示:
- 字符都是英文字母。
- 字符串长度在[1, 9]之间。
Submission
运行时间: 22 ms
内存: 16.0 MB
class Solution:
def permutation(self, S: str) -> List[str]:
n=len(S)
if n==0:
return [""]
res=[]
for i in range(n):
if S[i] in S[:i]: #只需判断S[i]是否在S[:i]中出现过即可
continue
for s1 in self.permutation(S[:i]+S[i+1:]):
res.append(S[i]+s1)
return res
Explain
此题解采用了递归回溯的方法来生成字符串的所有排列组合。首先，对给定字符串的每一个字符，将其作为当前排列的第一个字符，然后对剩余的字符再进行排列。为了避免重复的排列，通过检查当前字符是否在它前面的字符中出现过来跳过重复的情况。这样可以确保每个字符在每个位置上只被使用一次。每一层递归都会减少一个字符，直到字符串为空，此时返回包含空字符串的数组。
时间复杂度: O(n * n!)
空间复杂度: O(n!)
class Solution:
def permutation(self, S: str) -> List[str]:
n=len(S)
if n==0:
return ['']
res=[]
for i in range(n):
# 避免重复处理相同的字符
if S[i] in S[:i]:
continue
# 递归处理剩余部分
for s1 in self.permutation(S[:i]+S[i+1:]):
res.append(S[i]+s1)
return res
Explore
在递归回溯的过程中，通过设置一个判断条件来检查当前字符是否已经在前面被选作排列的一部分。具体来说，在每次选择一个字符作为当前排列的第一个字符时，我会检查这个字符是否在它之前的位置出现过。如果出现过，就跳过这个字符，防止生成重复的排列组合。这种方法确保了每个字符在每个位置只被使用一次，从而有效避免了重复处理相同的字符。
这种方法在所有情况下都是有效的，前提是输入的字符串是预先排序的。如果字符串未排序，相同的字符可能分布在字符串的不同位置，导致在不同的递归层级被重复处理。因此，在使用这种策略之前确保字符串是排序的可以避免这种情况。如果字符串已经排序，那么检查当前字符是否已在它之前的位置出现过，可以确保不会生成重复的排列组合，因为每次递归都会处理不包含当前已经选择字符的剩余部分。
在当前的解决方案中，没有直接考虑字符的频率或其他属性来优化性能。这种基本的递归回溯方法主要侧重于简单地生成所有可能的排列，而不考虑输入字符串中字符的具体属性。然而，可以通过一些优化策略来提高效率，例如使用计数排序或哈希表来记录每个字符的出现次数，然后基于这些统计数据来减少不必要的递归调用。例如，如果某个字符已经用完其出现次数，就不再进行递归。这样的优化可以在保持算法简洁性的同时，减少计算量，特别是对于包含重复字符较多的字符串。