Python查找无重复变位词代码编写咨询 现有实现逻辑求验证

原代码逻辑评估 #

• 正确性：最终输出的去重结果是对的，但逻辑设计冗余、效率极低，不适合长度超过6个字符的单词使用。
• 具体问题：
  • 每次执行unique[i] in unique[i+1:]都是O(n)的遍历操作，整体时间复杂度达到O(n²)，而permutations生成的排列数是原单词长度的阶乘，哪怕是8个字符的单词，排列数就已经超过4万，O(n²)的逻辑会卡顿非常明显。
  • 先把所有排列全量存入unique列表的操作会占用大量内存，长单词场景下会直接占满内存。
  • 你使用的getString不是Python标准库方法，标准库获取用户输入应该用input('Insert ')。

更高效的实现方案 #

方案1：快速改造现有逻辑（最小改动） #

直接利用Python内置的set结构自动去重，不需要自己写循环判断，代码量大幅减少，效率提升非常明显：

from itertools import permutations

seq = input('Insert ')
# 排列拼接为字符串后传入set自动去重，再转为列表
unique_anagrams = list(set(''.join(p) for p in permutations(seq)))

这个方案适合单词长度较短、重复字符少的场景，如果你只是做练习题交作业，这个方案足够用。

方案2：最优性能方案（适配含大量重复字符/长单词场景） #

如果原单词有很多重复字符，permutations还是会生成大量重复的无效排列，我们可以用回溯+字符计数的方式，直接生成唯一的变位词，完全不会产生重复项，避免无效计算：

from collections import Counter

def get_unique_anagrams(s):
    res = []
    char_cnt = Counter(s)
    chars = list(char_cnt.keys())
    cnts = list(char_cnt.values())
    total_len = len(s)

    def backtrack(path):
        if len(path) == total_len:
            res.append(''.join(path))
            return
        for idx in range(len(chars)):
            if cnts[idx] == 0:
                continue
            cnts[idx] -= 1
            path.append(chars[idx])
            backtrack(path)
            path.pop()
            cnts[idx] += 1
    
    backtrack([])
    return res

seq = input('Insert ')
unique_anagrams = get_unique_anagrams(seq)

这个方案的计算量只和实际存在的唯一变位词数量挂钩，比用permutations的方案性能高数十倍，尤其是原单词重复字符多的时候优势更突出。

内容的提问来源于stack exchange，提问作者PwNzDust