Python实现基于主列表前缀匹配的字符串最短通配符生成

输入定义 #

• 主列表 master_list：字符串集合，本场景下为API调用名称列表，包含输入列表中所有合法字符串
• 输入列表 input_list：字符串集合，每个元素均存在于master_list中，无需覆盖主列表全部元素

输出要求 #

使用*作为通配符（匹配规则为匹配零个或多个任意字符）对输入列表做模式压缩，需满足两个核心要求：

• 准确性：所有通配符模式匹配到的master_list元素必须全部属于input_list，不得额外引入主列表中未出现在输入列表内的项
• 最短性：尽可能减少输出列表的元素总数，同时尽可能缩短每个通配符的长度，以总字节占用最小为核心优化目标

实现约束 #

• 数据规模：master_list与input_list的长度均为O(50)量级，对算法时间复杂度容忍度高，常规Python实现即可轻松承载计算开销
• 前置处理：调用实现函数前，会对两个列表的所有字符串统一调用.lower()方法转换为小写，实现逻辑无需处理大小写兼容问题
• 输入校验：已提前完成合法性校验，保证input_list所有元素均存在于master_list中，实现逻辑无需处理非法输入场景

参考示例 #

master_list = [ "getfoo", "getbar", "getbaz", 
  "putfoo", "putbar", "putbaz", "putfoothing", "putfoootherthing",
  "viewfoo", "viewbar", "viewbarthing", "viewbaz" ]

input_list = [ "getbar", "getbaz", "putfoootherthing", "viewbar", "viewbarthing" ]

# 预期正确输出
correct_output_list = [ "getb*", "putfooo*", "viewbar*" ]

# 错误输出示例
wrong_output_list = [ "get*", "putfoootherthing", "viewb*" ]

正确输出判定规则 #

• getb*匹配主列表中的getbar、getbaz，二者均属于输入列表，范围准确
• putfooo*仅匹配主列表中的putfoootherthing，使用通配符后比原字符串更短，符合字节节省目标
• viewbar*匹配主列表中的viewbar、viewbarthing，且不会匹配不在输入列表中的viewbaz，范围准确

错误输出问题说明 #

• get*匹配范围过宽，会引入不在输入列表中的getfoo，不符合准确性要求
• putfoootherthing未使用通配符做压缩，没有尽可能缩短字符串长度，不符合最短性要求
• viewb*匹配范围过宽，会引入不在输入列表中的viewbaz，不符合准确性要求

实现思路 #

由于数据规模极小，可直接通过贪心枚举实现，且最优解中的通配符一定位于模式末尾（非末尾的通配符要么匹配范围不可控，要么无法进一步缩短长度，无枚举必要）：

1. 维护待覆盖集合，初始为input_list的全集
2. 每轮枚举所有待覆盖字符串的所有可能前缀，拼接*作为候选模式
3. 校验候选模式合法性：收集master_list中所有匹配该模式的元素，若存在元素不在input_list中则直接淘汰该模式
4. 选择本轮最优模式：优先选择覆盖待处理元素最多的模式，覆盖数量相同时选择模式本身长度最短的
5. 将最优模式加入结果集，从待覆盖集合中移除该模式匹配到的所有元素，重复上述流程直到待覆盖集合为空

参考实现代码 #

def compress_api_list(master_list: list[str], input_list: list[str]) -> list[str]:
    master_set = set(master_list)
    input_set = set(input_list)
    uncovered = set(input_set)
    result = []

    def is_match(pattern: str, target: str) -> bool:
        # 所有合法模式均为「前缀+*」格式，直接做前缀匹配即可
        prefix = pattern[:-1]
        return target.startswith(prefix)

    while uncovered:
        best_pattern = None
        best_cover = set()
        # 遍历所有未覆盖字符串生成候选模式
        for api_str in uncovered:
            # 枚举所有可能的前缀长度，从最短到最长
            for prefix_len in range(1, len(api_str) + 1):
                prefix = api_str[:prefix_len]
                candidate = f"{prefix}*"
                # 收集主列表中所有匹配该模式的元素
                matched = {m for m in master_set if is_match(candidate, m)}
                # 越界则模式非法
                if not matched.issubset(input_set):
                    continue
                # 计算该模式能覆盖的未处理元素
                current_cover = matched & uncovered
                # 按「覆盖数最多、模式最短」规则选最优
                if (len(current_cover) > len(best_cover)) or \
                   (len(current_cover) == len(best_cover) and (best_pattern is None or len(candidate) < len(best_pattern))):
                    best_pattern = candidate
                    best_cover = current_cover
        result.append(best_pattern)
        uncovered -= best_cover
    return sorted(result)

# 示例测试
if __name__ == "__main__":
    master_list = [ "getfoo", "getbar", "getbaz", 
      "putfoo", "putbar", "putbaz", "putfoothing", "putfoootherthing",
      "viewfoo", "viewbar", "viewbarthing", "viewbaz" ]
    input_list = [ "getbar", "getbaz", "putfoootherthing", "viewbar", "viewbarthing" ]
    print(compress_api_list(master_list, input_list))
    # 输出结果：['getb*', 'putfooo*', 'viewbar*']，与预期完全一致

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