Python中复杂列表匹配：判断listA是否为listB的有序子序列

需求说明 #

判断列表listB是否包含listA的全部元素，且元素顺序与listA完全一致，允许listB存在额外或穿插元素。匹配失败时，需定位第一个未匹配的元素并给出提示。

实现代码 #

def check_ordered_subsequence(list_a, list_b):
    ptr_a = 0
    len_a = len(list_a)
    if len_a == 0:
        return True, ""
    
    for elem in list_b:
        if elem == list_a[ptr_a]:
            ptr_a += 1
            if ptr_a == len_a:
                break
    
    if ptr_a == len_a:
        return True, ""
    else:
        missing_elem = list_a[ptr_a]
        return False, f"{missing_elem}缺失"

测试示例 #

• 匹配成功场景1：

  listA = ['A','B','C','D','E']
  listB = [':','A','*','B','C','D','E','`']
  print(check_ordered_subsequence(listA, listB))  # 输出: (True, '')
  

• 匹配成功场景2：

  listA = ['A','B','C','D','E']
  listB = ['A','*','C','B','C','D','E']
  print(check_ordered_subsequence(listA, listB))  # 输出: (True, '')
  

• 匹配失败场景1（元素缺失）：

  listA = ['A','B','C','D','E']
  listB = ['A','B','C','D','F']
  print(check_ordered_subsequence(listA, listB))  # 输出: (False, 'E缺失')
  

• 匹配失败场景2（长度不足）：

  listA = ['A','B','C','D','E']
  listB = ['A','B','C','D']
  print(check_ordered_subsequence(listA, listB))  # 输出: (False, 'E缺失')
  

逻辑说明 #

1. 用指针ptr_a追踪listA的当前匹配位置
2. 遍历listB，每匹配到listA的当前元素就移动指针
3. 若指针走完listA所有元素，说明匹配成功
4. 若遍历完listB仍未匹配完listA，则第一个未匹配的元素即为缺失项

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