Python求解从source字符串构建target字符串的所有可行方式

核心逻辑 #

这是典型的子序列匹配需求，要求从source字符串中按原字符顺序选取若干字符，恰好拼接为target字符串，同时输出所有合法选取方案的带标记原串。

完整可运行代码 #

def generate_marked_source(source, selected_indices):
    # 把选中的索引按连续区间分组
    selected = sorted(selected_indices)
    groups = []
    current_group = [selected[0]]
    for idx in selected[1:]:
        if idx == current_group[-1] + 1:
            current_group.append(idx)
        else:
            groups.append(current_group)
            current_group = [idx]
    groups.append(current_group)
    # 生成带括号的字符串
    group_start = {g[0] for g in groups}
    group_end = {g[-1] for g in groups}
    res = []
    for i, c in enumerate(source):
        if i in group_start:
            res.append('(')
        res.append(c)
        if i in group_end:
            res.append(')')
    return ''.join(res)

def count_and_list_subsequences(source, target):
    m, n = len(source), len(target)
    # 存储所有合法路径：每个路径是匹配target对应位置的source下标列表
    result_paths = []
    
    def backtrack(s_idx, t_idx, current_path):
        if t_idx == n:
            result_paths.append(current_path.copy())
            return
        if s_idx == m:
            return
        # 选中当前source字符，如果和target当前位置匹配
        if source[s_idx] == target[t_idx]:
            current_path.append(s_idx)
            backtrack(s_idx + 1, t_idx + 1, current_path)
            current_path.pop()
        # 不选中当前source字符
        backtrack(s_idx + 1, t_idx, current_path)
    
    backtrack(0, 0, [])
    # 生成标记后的字符串，去重
    marked_results = list({generate_marked_source(source, path) for path in result_paths})
    return len(marked_results), marked_results

# 示例运行
if __name__ == "__main__":
    source = "cattcat"
    target = "cat"
    count, results = count_and_list_subsequences(source, target)
    print(f"符合要求的构建方式共{count}种，分别为：")
    for res in results:
        print(res)

运行结果 #

示例参数运行后输出如下：

符合要求的构建方式共5种，分别为：
(cat)tcat
(ca)t(t)cat
(ca)ttca(t)
(c)attc(at)
catt(cat)

功能说明 #

• 支持任意长度的source和target输入，自动处理边界情况（比如target比source长直接返回0种）
• 自动对结果去重，避免重复的标记字符串输出
• 标记格式完全符合示例要求，连续选中的字符放在同一对括号内

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