匹配带通配符的两个列表的算法

Question

我在寻找一种高效的方法来匹配两个列表，一个列表包含完整的信息，另一个列表包含通配符。我之前已经能处理固定长度的通配符，现在想尝试处理可变长度的通配符。

也就是说：

match( ['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D'] )

只要两个列表中的所有元素顺序相同，就会返回True。

我正在处理对象的列表，但为了简单起见，上面用了字符串。

Answer 1

我建议把 ['A', 'B', '*', 'D'] 转换成 '^AB.*D$'，把 ['A', 'B', 'C', 'C', 'C', 'D'] 转换成 'ABCCCD'，然后使用 re 模块（正则表达式）来进行匹配。

这样做是有效的，前提是你列表里的每个元素都是一个字符，并且它们是字符串。

像这样：

import(re)
def myMatch( patternList, stringList ):
    # convert pattern to flat string with wildcards
    # convert AB*D to valid regex ^AB.*D$
    pattern = ''.join(patternList) 
    regexPattern = '^' + pattern.replace('*','.*') + '$' 
    # perform matching
    against = ''.join(stringList) # convert ['A','B','C','C','D'] to ABCCCD
    # return whether there is a match
    return (re.match(regexPattern,against) is not None)

如果列表里包含数字或者单词，选择一个你不希望出现在其中的字符，比如 #。这样 ['Aa','Bs','Ce','Cc','CC','Dd'] 就可以转换成 Aa#Bs#Ce#Cc#CC#Dd，而通配符模式 ['Aa','Bs','*','Dd'] 可以转换成 ^Aa#Bs#.*#Dd$，然后进行匹配。

实际上，这意味着在 myMatch 中，所有的 ''.join(...) 都变成了 '#'.join(...)。

Answer 2

下面的内容怎么样：

import re

def match(pat, lst):
  regex = ''.join(term if term != '*' else '.*' for term in pat) + '$'
  s = ''.join(lst)
  return re.match(regex, s) is not None

print match( ['A', 'B', '*', 'D'], ['A', 'B', 'C', 'C', 'C', 'D'] )

它使用了正则表达式。通配符（*）被替换成了.*，而其他的搜索词则保持不变。

有一点需要注意的是，如果你的搜索词中可能包含在正则表达式中有特殊含义的字符，那么这些字符需要被正确处理。其实在match函数中处理这个问题很简单，只是我不确定这是否是你需要的。

Answer 3

[编辑以说明在OP评论中没有使用正则表达式来比较对象]

看起来你不是在使用字符串，而是在比较对象。因此，我给出一个明确的算法——正则表达式确实是处理字符串的好方法，别误解我的意思，但根据你在问题评论中的说法，似乎一个简单明了的算法会让事情变得更简单。

实际上，这个问题可以用比之前的回答更简单的算法来解决：

def matcher (l1, l2):
    if (l1 == []):
        return (l2 == [] or l2 == ['*'])
    if (l2 == [] or l2[0] == '*'):
        return matcher(l2, l1)
    if (l1[0] == '*'):
        return (matcher(l1, l2[1:]) or matcher(l1[1:], l2))
    if (l1[0] == l2[0]):
        return matcher(l1[1:], l2[1:])
    else:
        return False

关键的想法是，当你遇到一个通配符时，你可以选择两种方式：

• 要么在包含通配符的列表中向前移动（并认为通配符匹配到目前为止的任何内容）
• 要么在不包含通配符的列表中向前移动（并认为列表开头的内容必须被通配符匹配）。