1

我正在寻找将单个字符串的结尾与预定义字符串列表中的值匹配的最佳最 有效方法。
就像是 

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的字符串方法，但这并不是我所需要的。此外，我的问题不能概括为使用模块或类似的解决，因为它是一个字符串问题，而不是一个路径问题。背景结束 我以这两种方式提出了我的方法 os

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

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

谢谢。

4

1 回答 1

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

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

于 2018-07-12T01:12:56.580 回答