python - 匹配字符串结尾

Question

我正在寻找最高效的最佳方法来将单个字符串的结尾与预定义字符串列表中的值进行匹配。
类似的东西

my_str='QWERTY'
my_lst=['QWE','QQQQ','TYE','YTR','TY']  

match='TY' 或 match=['TY']

在限制下

len(my_lst) 已知，但任意，因此可能很长，可能在 30 左右
my_lst 中的元素可能具有不同的 len，因此我不能每次都检查 my_str 定义的最后部分
对于 my_str 以及 my_lst 中的匹配元素，它们可以是字符串或列表，以效率更高者为准(参见背景)
len(my_str) 大部分都很小，不超过 8 个字符
in 函数不会执行此操作，因为我需要仅在末尾进行匹配。
endswith 本身没有任何用处，因为它只会返回一个 bool 值
匹配项应始终是唯一的或 []，因为 my_lst 中的任何元素都不会彼此共享结尾

小背景可以跳过
我开始将此问题作为一个列表问题，例如 ['Q','W','E','R','T','Y'] ，其中我将有一个列表用于匹配的 1 个字符串列表，我正在考虑运行一个反向迭代作为 [::-1] 来检查每个候选者。
然后我意识到可以连接内部列表，因为它们仅包含字符串并对结果字符串运行相同的逻辑。
最后我遇到了 endswith 字符串方法读取 this question但这并不完全是我所需要的。此外，我的问题不能概括为使用 os 模块或类似模块来解决，因为它是一个字符串问题，而不是路径问题。
背景结束
我用这两种方式实现了我的方法

match=filter(lambda x: my_str.endswith(x), my_lst)
match=[x for x in my_lst if my_str.endswith(x)]

我成功了，但我想知道是否有一些内置或最佳方法来查找并返回匹配的结束值。

谢谢。

Answer 1

这是一种使用 trie 的方法，或前缀树(在这种情况下技术上是后缀树)。如果我们有三个潜在的后缀 CA、CB 和 BA，我们的后缀树将如下所示

     e
    / \
  A     B
 / \    |
B   C   C

(e 是空字符串)我们从输入字符串的末尾开始并消耗字符。如果我们遇到字符串的开头或不是当前节点子节点的字符，那么我们会拒绝该字符串。如果我们到达了树上的一片叶子，那么我们就接受了该字符串。这使我们能够更好地扩展到许多潜在的后缀。

def build_trie(suffixes):
    head = {}
    for suffix in suffixes:
        curr = head
        for c in reversed(suffix):
            if c not in curr:
                curr[c] = {}
            curr = curr[c]
    return head

def is_suffix(trie, s):
    if not trie:
        return True
    for c in reversed(s):
        try:
            trie = trie[c]
        except KeyError:
            return False
        if not trie:
            return True
    return False

trie = build_trie(['QWE','QQQQ','TYE','YTR','TY'])

给我们一个尝试

{'E': {'W': {'Q': {}}, 
       'Y': {'T': {}}},
 'Q': {'Q': {'Q': {'Q': {}}}},
 'R': {'T': {'Y': {}}},
 'Y': {'T': {}}}

如果您想返回匹配的后缀，只需跟踪我们在trie树中下降时看到的字符即可。

def has_suffix(trie, s):
    if not trie:
        return ''
    letters = []
    for c in reversed(s):
        try:
            trie = trie[c]
            letters.append(c)
        except KeyError:
            return None
        if not trie:
            return ''.join(letters)
    return None

值得注意的是，build_trie(['']) 和 build_trie([]) 都可以访问空 trie，并且匹配空字符串所有字符串的末尾。为了避免这种情况，您可以检查 suffixes 的长度并返回一些非字典值，您可以在 has_suffix

中检查该值