[已解决]力扣 面试题08.08有重复字符串的排列组合

PlanY

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例 1：

输入：S = "qqe"
输出：["eqq","qeq","qqe"]
示例 2：

输入：S = "ab"
输出：["ab", "ba"]

1. class Solution:
   
2.     def permutation(self, S: str) -> List[str]:
   
3.         S = sorted(S)
   
4.         n = len(S)
   
5.         check = [False] * n
   
6.         path = []
   
7.         ans = []
   
8. 
   
9.         @cache
   
10.         def dfs():
    
11.             if len(path) == n:
    
12.                 ans.append(''.join(path))
    
13.                 return
    
14. 
    
15.             for i in range(n):
    
16.                 if check[i]:
    
17.                     continue
    
18.                 if i > 0 and S[i] == S[i - 1] and not check[i - 1]:
    
19.                     continue
    
20. 
    
21.                 check[i] = True
    
22.                 path.append(S[i])
    
23.                 dfs()
    
24.                 path.pop()
    
25.                 check[i] = False
    
26. 
    
27.         dfs()
    
28.         return ans

复制代码

以上是题目与我的答案，为什么我的代码只能返回其中一个合法字符串，而不是所有合法字符串？

最佳答案

月排行榜 / 总排行榜

FishC

2025-8-8 09:57:42

您的代码存在几个关键问题导致只能返回一个结果。主要问题在于：

1. **变量初始化错误**：`check =  * n` 和 `path = ` 语法错误
2. **缺少函数参数**：`dfs()` 函数没有参数导致状态无法回溯
3. **缓存装饰器误用**：`@cache` 会阻止递归调用
4. **去重逻辑错误**：条件判断 `S == S` 应为 `S[i] == S[i-1]`

修正后的代码：

1. 
   
2. class Solution:
   
3.     def permutation(self, S: str) -> List[str]:
   
4.         S = sorted(S)  # 排序使相同字符相邻
   
5.         n = len(S)
   
6.         check = [False] * n  # 标记访问状态
   
7.         path = []  # 当前路径
   
8.         ans = []   # 结果集
   
9. 
   
10.         def dfs():
    
11.             if len(path) == n:
    
12.                 ans.append(''.join(path))
    
13.                 return
    
14.             
    
15.             for i in range(n):
    
16.                 # 跳过已访问或重复未访问字符
    
17.                 if check[i]:
    
18.                     continue
    
19.                 if i > 0 and S[i] == S[i-1] and not check[i-1]:
    
20.                     continue
    
21.                
    
22.                 # 选择当前字符
    
23.                 check[i] = True
    
24.                 path.append(S[i])
    
25.                 dfs()  # 递归探索
    
26.                 # 回溯
    
27.                 path.pop()
    
28.                 check[i] = False
    
29.                
    
30.         dfs()
    
31.         return ans
    

复制代码

关键修正点：
1. 使用 check = [False] * n 初始化访问数组
2. 移除 @cache 装饰器（会阻止递归）
3. 修正去重条件为：S[i] == S[i-1] and not check[i-1]
4. 正确初始化 path = []

算法逻辑：
1. 排序字符串使相同字符相邻
2. DFS回溯时跳过：
   - 已使用的字符（check[i]==True）
   - 与前字符相同且前字符未被使用的情况（避免重复排列）
3. 当路径长度等于原字符串时，记录有效排列

示例运行：
输入 "qqe" 输出：['eqq', 'qeq', 'qqe']
输入 "ab" 输出：['ab', 'ba']

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

您的代码存在几个关键问题导致只能返回一个结果。主要问题在于：

1. **变量初始化错误**：`check =  * n` 和 `path = ` 语法错误
2. **缺少函数参数**：`dfs()` 函数没有参数导致状态无法回溯
3. **缓存装饰器误用**：`@cache` 会阻止递归调用
4. **去重逻辑错误**：条件判断 `S == S` 应为 `S[i] == S[i-1]`

修正后的代码：

1. 
   
2. class Solution:
   
3.     def permutation(self, S: str) -> List[str]:
   
4.         S = sorted(S)  # 排序使相同字符相邻
   
5.         n = len(S)
   
6.         check = [False] * n  # 标记访问状态
   
7.         path = []  # 当前路径
   
8.         ans = []   # 结果集
   
9. 
   
10.         def dfs():
    
11.             if len(path) == n:
    
12.                 ans.append(''.join(path))
    
13.                 return
    
14.             
    
15.             for i in range(n):
    
16.                 # 跳过已访问或重复未访问字符
    
17.                 if check[i]:
    
18.                     continue
    
19.                 if i > 0 and S[i] == S[i-1] and not check[i-1]:
    
20.                     continue
    
21.                
    
22.                 # 选择当前字符
    
23.                 check[i] = True
    
24.                 path.append(S[i])
    
25.                 dfs()  # 递归探索
    
26.                 # 回溯
    
27.                 path.pop()
    
28.                 check[i] = False
    
29.                
    
30.         dfs()
    
31.         return ans
    

复制代码

关键修正点：
1. 使用 check = [False] * n 初始化访问数组
2. 移除 @cache 装饰器（会阻止递归）
3. 修正去重条件为：S[i] == S[i-1] and not check[i-1]
4. 正确初始化 path = []

算法逻辑：
1. 排序字符串使相同字符相邻
2. DFS回溯时跳过：
   - 已使用的字符（check[i]==True）
   - 与前字符相同且前字符未被使用的情况（避免重复排列）
3. 当路径长度等于原字符串时，记录有效排列

示例运行：
输入 "qqe" 输出：['eqq', 'qeq', 'qqe']
输入 "ab" 输出：['ab', 'ba']

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。