检查String是否是列表中元素的串联

是否有一种优雅的方式(最好是pythonic)来检查String s是否是一组L的子集的元素串联？L的元素可能在s中出现不止一次.

例如:

L = set(["a", "ab", "c", "e"])

然后"abac"是L的子集的元素的有效串联

"aaaaaaa"也是一种有效的连接.

但"广告"不是因为"d"不在L.

1> greggo..：

---

import re
L = ["no", "force", "in", "the", "verse", "can", "stop", "me"]
# make this: "(?:no|force|in|the|verse|can|stop|me)*$"
r = re.compile( "(?:" + "|".join(L) + ")*$")
r.match("shiny")  # -> None
r.match("canme")  # -> not None

这适用于给定的字符串集.re库中有一个函数可以引用字符串(转义 |等),以便您可以在运行时安全地创建这样的表达式.

r = re.compile( "(?:"  + "|".join( re.escape(s) for s in L) + ")*$" )

无论子串出现多少次,它都会匹配; 如果某些字符串是其他字符串的前缀,则可能会出现奇怪的结果,等等.它可能有令人讨厌的运行时.如果所有字符串在开头都很容易区分,那就不应该.

---

不,实际上这个可以运行得非常快,也许是线性时间.这是一个有限状态自动机.

---

@xiamx但是如果你有"ab"和"alon"和"abalone","沿着"和"gnu"等等,可能会有很多反向追踪？但是如果没有共同的前缀,它应该只是在每个字符串出现时识别它们并继续前进到下一个字符串.