python - 匹配字符串结尾
问题描述
我正在寻找将单个字符串的结尾与预定义字符串列表中的值匹配的最佳最 有效方法。
就像是
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)]
我成功了,但我想知道是否有一些内置或最佳方法来查找并返回匹配的结束值。
谢谢。
解决方案
这是一种使用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
推荐阅读
- python - 如何设置双循环以从左上角到右下角扫描图像?
- recursion - StandardML 因子评估在 Poly/ML REPL 中进入无限循环
- java - Rest API ResponseEntity 为响应添加额外的属性
- r - list.files 考虑到 R 中的列表编号?
- reactjs - React Material UI Table/Data Grid 仅显示行但不显示列
- spring - 可以在 Rest Controller 中使用对象数组吗
- python - 在 Backtrader 问题中获取数据
- python - Pandas:创建一个班次指标,省略组的第一个值
- javascript - 结束日期必须小于开始日期,Vuelidate 和 VueJs
- windows - 命令提示符作为管理员使用实际用户的 %username% 变量