力扣 面试题08.08有重复字符串的排列组合
有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。示例 1：
输入：S = "qqe"
输出：["eqq","qeq","qqe"]
示例 2：
输入：S = "ab"
输出：["ab", "ba"]
class Solution:
def permutation(self, S: str) -> List:
S = sorted(S)
n = len(S)
check = * n
path = []
ans = []
@cache
def dfs():
if len(path) == n:
ans.append(''.join(path))
return
for i in range(n):
if check:
continue
if i > 0 and S == S and not check:
continue
check = True
path.append(S)
dfs()
path.pop()
check = False
dfs()
return ans
以上是题目与我的答案，为什么我的代码只能返回其中一个合法字符串，而不是所有合法字符串？ 您的代码存在几个关键问题导致只能返回一个结果。主要问题在于：
1. **变量初始化错误**：`check =* n` 和 `path = ` 语法错误
2. **缺少函数参数**：`dfs()` 函数没有参数导致状态无法回溯
3. **缓存装饰器误用**：`@cache` 会阻止递归调用
4. **去重逻辑错误**：条件判断 `S == S` 应为 `S == S`
修正后的代码：
class Solution:
def permutation(self, S: str) -> List:
S = sorted(S)# 排序使相同字符相邻
n = len(S)
check = * n# 标记访问状态
path = []# 当前路径
ans = [] # 结果集
def dfs():
if len(path) == n:
ans.append(''.join(path))
return
for i in range(n):
# 跳过已访问或重复未访问字符
if check:
continue
if i > 0 and S == S and not check:
continue
# 选择当前字符
check = True
path.append(S)
dfs()# 递归探索
# 回溯
path.pop()
check = False
dfs()
return ans
关键修正点：
1. 使用 check = * n 初始化访问数组
2. 移除 @cache 装饰器（会阻止递归）
3. 修正去重条件为：S == S and not check
4. 正确初始化 path = []
算法逻辑：
1. 排序字符串使相同字符相邻
2. DFS回溯时跳过：
- 已使用的字符（check==True）
- 与前字符相同且前字符未被使用的情况（避免重复排列）
3. 当路径长度等于原字符串时，记录有效排列
示例运行：
输入 "qqe" 输出：['eqq', 'qeq', 'qqe']
输入 "ab" 输出：['ab', 'ba']
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]