求解子序列在字符串中匹配时最少中断次数的算法问题

问题描述 #

给定查询串（subsequence）和目标字符串（sequence），需计算目标字符串中可拼接得到查询串的连续字符分组的最小数量，也就是分组之间的最少中断次数，要求字符顺序严格匹配：abc不会被识别为出现在cba中。

示例说明 #

• 示例1：查询串为abcjkl，目标串为a_b_c_abc_j_k_l_jkl，期望结果为2个分组。最优匹配为abc和jkl的组合，优先于a、b、c加jkl的4分组方案，因为中断次数更少。两个分组在目标串中的间隔字符不影响计数，仅计1次中断。
• 示例2：查询串为abcjkl，目标串为abc_jkl_abcj_kl，期望结果为2个分组，abc+jkl或者abcj+kl的方案均符合要求。

实现思路 #

要得到最少分组数，最优策略是每次匹配尽可能长的连续子串，采用双指针贪心方案即可：

1. 分别维护查询串的已匹配位置指针、目标串的已遍历位置指针
2. 每开启一轮匹配，分组计数+1，从当前目标串位置开始，尽可能匹配查询串的后续字符
3. 本轮匹配结束后，更新目标串的遍历起始位置，直到查询串所有字符匹配完成

参考代码（Python） #

def min_matching_groups(subseq: str, sequence: str) -> int:
    sub_ptr = 0
    seq_ptr = 0
    group_count = 0
    len_sub = len(subseq)
    len_seq = len(sequence)
    
    while sub_ptr < len_sub:
        group_count += 1
        current_seq_pos = seq_ptr
        # 尽可能匹配最长的连续段
        while current_seq_pos < len_seq and sub_ptr < len_sub:
            if sequence[current_seq_pos] == subseq[sub_ptr]:
                sub_ptr += 1
            current_seq_pos += 1
        seq_ptr = current_seq_pos
    return group_count

验证结果 #

• 示例1调用 min_matching_groups("abcjkl", "a_b_c_abc_j_k_l_jkl")，返回结果为2，符合预期
• 示例2调用 min_matching_groups("abcjkl", "abc_jkl_abcj_kl")，返回结果为2，符合预期

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