匹配字符串结尾

Question

我正在寻找最好的 most efficient 方法来匹配单个字符串的结尾与预定义列表中的值字符串。
像

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 本身没有用，因为它只会 return 一个 Boolean
匹配应该始终是唯一的或 [] 因为 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)]

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

谢谢。

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': {}}}

如果您想要 return 匹配的后缀，这只是跟踪我们在下降 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 和 return 的一些非字典值的长度，您将在 has_suffix

中检查这些值

匹配字符串结尾

matching end of string

python

string

slice

ends-with