使用permutation判断字符串互为排列组合时返回False问题排查

现有代码的核心问题 #

• 循环逻辑错误：你的代码在遍历排列结果的第一轮就会直接返回结果，只要第一个排列和目标字符串不匹配，就直接返回False，不会检查后续的排列组合。itertools.permutations('apple')返回的第一个排列是原字符串apple，测试用例appel第一次比对不通过就直接返回了False，和预期不符。
• 缺少长度校验：两个字符串如果长度不一致，不可能互为排列组合，无需生成排列即可直接返回False，你的代码缺少这一步判断，会做很多无用计算。
• 性能缺陷：生成全排列的时间复杂度为O(n!)，字符串长度超过10之后运行速度会变得极慢，不适合实际场景使用。

基于原有逻辑的修复代码 #

保留使用itertools.permutations的逻辑，修复循环错误并增加长度校验：

import itertools

def gen(char, phrase):
    # 长度不一致直接返回False
    if len(char) != len(phrase):
        return False
    # 生成所有排列后直接判断目标是否存在
    return phrase in set(map(''.join, itertools.permutations(char)))

print(gen('apple', 'appel')) # 预期返回True，实际返回True
print(gen('apple', 'elppa')) # 预期返回True，实际返回True
print(gen('apple', 'ap')) # 预期返回False，实际返回False

更高效的实现方案（推荐） #

判断两个字符串是否互为排列不需要生成全排列，两种更简单的方案性能提升极大：

方案1：排序后比对 #

互为排列的字符串排序后结果完全一致，时间复杂度O(nlogn)：

def is_permutation(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    return sorted(s1) == sorted(s2)

方案2：统计字符出现频率 #

统计每个字符的出现次数，所有字符次数一致则互为排列，时间复杂度O(n)：

def is_permutation(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    # 仅适配小写字母场景，如需支持全ASCII可将数组长度改为128
    char_count = [0] * 26
    for c in s1:
        char_count[ord(c) - ord('a')] += 1
    for c in s2:
        char_count[ord(c) - ord('a')] -= 1
        if char_count[ord(c) - ord('a')] < 0:
            return False
    return all(count == 0 for count in char_count)

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