如何在Python中利用查找表实现字符串的多组合替换？

现有代码仅能将字符串按单个单词拆分后替换为查找表中的缩写：

case = ["MY_FIRST_RODEO"]
lookup = {'MY': 'M', 'FIRST': 'FRST', 'RODEO' : 'RD', 'FIRST_RODEO': 'FRD', 'MY_FIRST': 'MF', 'MY_FIRST_RODEO': 'MFR'}
case_mod = []
for string in case:
    words = string.split("_")
    new_string = [lookup[word] for word in words]
    case_mod.append("_".join(new_string))
print(case_mod)

输出结果：

['M_FRST_RD']

但需要生成所有可能的替换组合（包含多单词组合的缩写），期望输出：

['M_FRST_RD', 'MF_RD', 'M_FRD', 'MFR']

已能拆分出所有可能的子串，但无法将拆分与替换逻辑结合，以下是解决方案：

解决方案 #

核心思路是枚举所有不重叠的连续子串分割方式，确保每个子串都存在于查找表中，再将每个子串替换为对应缩写后拼接，最终去重得到所有结果。

实现代码 #

case = ["MY_FIRST_RODEO"]
lookup = {'MY': 'M', 'FIRST': 'FRST', 'RODEO' : 'RD', 'FIRST_RODEO': 'FRD', 'MY_FIRST': 'MF', 'MY_FIRST_RODEO': 'MFR'}

def generate_all_abbreviations(words, lookup):
    results = set()
    n = len(words)
    
    def backtrack(start, current_parts):
        if start == n:
            results.add("_".join(current_parts))
            return
        # 尝试从start开始的所有可能长度的连续子串
        for end in range(start + 1, n + 1):
            substring = "_".join(words[start:end])
            if substring in lookup:
                backtrack(end, current_parts + [lookup[substring]])
    
    backtrack(0, [])
    return sorted(results)

for string in case:
    words = string.split("_")
    all_abbrs = generate_all_abbreviations(words, lookup)
    print(all_abbrs)

输出结果 #

['M_FRST_RD', 'M_FRD', 'MF_RD', 'MFR']

逻辑说明 #

1. 使用回溯法遍历所有可能的分割点：从当前起始索引start出发，尝试所有可能的结束索引end，将words[start:end]拼接成子串。
2. 若子串存在于查找表中，则将其对应的缩写加入当前片段列表，继续递归处理剩余的单词。
3. 当处理完所有单词（start == n），将拼接后的缩写字符串存入集合（自动去重）。
4. 最后返回排序后的结果集合。

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