Python中如何按顺序匹配所有关键词？求优化方案

需求 #

检查句子列表是否严格按关键词列表的顺序包含所有关键词，关键词不需要连续出现，但顺序不能乱。

示例 #

• 关键词列表：

keywords = ['Hello', 'my', 'friend']

• 不符合顺序（返回False）：

sentence = ['Dear', 'my', 'friend', 'Hello']

• 符合顺序（返回True）：

sentence = ['Hello', 'my', 'Dear', 'friend']

原有代码问题 #

下面的代码在句子存在重复关键词时会失效——因为index()方法只会返回第一个匹配的位置，导致判断逻辑出错：

keywords = ['Hello', 'my', 'friend']
sentence = ['Dear', 'my', 'friend', 'Hello']
marker = 0
for keyword in keywords:
    for word in sentence:
        if keyword == word:
            marker = sentence.index(word) - marker
            if marker < 0:
                return False
return True

优化方案：双指针法 #

用双指针可以高效解决这个问题，时间复杂度为O(n)（n是句子长度），还能正确处理重复词的情况：

def check_keyword_order(keywords, sentence):
    keyword_pos = 0
    total_keywords = len(keywords)
    # 空关键词列表直接返回True
    if total_keywords == 0:
        return True
    # 遍历句子中的每个词
    for word in sentence:
        # 匹配到当前目标关键词，就推进关键词指针
        if word == keywords[keyword_pos]:
            keyword_pos += 1
            # 所有关键词都匹配完成，直接返回True
            if keyword_pos == total_keywords:
                return True
    # 遍历完句子都没匹配完所有关键词，返回False
    return False

方法优势 #

• 只需要遍历一遍句子，效率更高。
• 遇到重复关键词时，会按顺序匹配下一个目标关键词，不会因为index()取第一个位置而出错。比如句子是['Hello', 'my', 'my', 'friend']，会正确匹配第一个Hello、第一个my，最后找到friend，返回True；如果句子是['my', 'Hello', 'friend']，匹配完my后，后续找不到Hello在my之后，最终返回False，完全符合需求。

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