bounty还有2天到期。此问题的答案有资格获得+50声望奖励。Savaratkar正在寻找一个答案从一个有信誉的来源。
是否有算法或代码/lib(*NodeJS首选 *),从一组字符串或文本中提取通配符字符串。
例如,以下是作为输入的字符串集合(*forgive my英语 *):
apple pie is not too so good
apple pie is not so good
apple pie is too good
我将能够提取一个通配符字符串只有星号 *,像这样:
apple pie is * good
通配符中还有其他特殊字符,但我只想使用 * 星号。
在某种程度上,我们可以说我需要从输入字符串中提取正则表达式。现在有没有一个库或算法来实现这一点?
请让我知道如果需要更多的信息。
3条答案
按热度按时间mf98qq941#
我假设您希望提取一个通配符,它将适用于所有字符串。如果没有,我不知道如何开始。
另外,在第一遍中,我将纠正您的英语,将
"apple pie is not too so good"
更改为"apple pie is not very good"
。原因将在下面清楚。为了解决这个问题,我们可以将其分解为找到所有字符串的公共前缀,以及所有字符串的公共后缀,并使用
*
通配符将它们连接在一起。它可能看起来像这样:我们的
commonPrefix
函数找到某个字符串与第一个字符串不同的第一个索引,然后将字符串切片到该点。commonSuffix
使用字符串reverse
辅助函数,反转所有字符串,找到它们的公共前缀并反转该值。(还有很多其他的方法可以做到这一点,其中一些更有效,但它们涉及到计算最长的字符串开始,并且都更复杂。如果这里有性能问题,我会考虑使用其中一个。)但是这里有一个问题,通过使用原始的
"apple pie is not too so good"
可以看出:通配符旁边的额外
o
是不需要的。为了解决这个问题,我们可以创建一个更复杂的extractWildcard
版本来处理空格:更新
下面是一个更高效的
commonSuffix
版本:我会坚持使用更简单的方法,除非这被证明是应用程序中的实际瓶颈。
更新二:简单性
(This不是关于实际问题,而是关于代码简单性的讨论;请随意忽略它。)
一条评论说:
即使对我来说,这也是一段几乎不可读的代码[...]。对于公共前缀确实存在更简单、更可读的算法。
我想就这一点进行辩论。Rich Hickey有一个著名的演讲,Simple Made Easy,它区分了“简单”和“容易”。* 简单 * 是一个相当客观的衡量标准,衡量的是有多少概念被缠绕在一起来提供一个解决方案。* 容易 * 是一个主观的衡量标准,衡量解决方案对特定人员的熟悉程度。
通过编写声明性代码,通过避免像可变状态这样的技术,通过使用表达式而不是语句,以及通过避免变量赋值的时间效应,我认为这段代码相当简单。它可能不熟悉,因此对某些用户来说可能不那么容易。
上面的代码是我写的;我没有从某个地方开始,把它削减到最低限度。但我们可以试试。我们可以从最命令式的--也是最熟悉的--代码风格开始:
这可能对一些人来说更 * 熟悉 / 容易 *。但让我们看看实现。我们有12个局部变量。我们使用一对嵌套循环,每个循环包含一个
if
语句。在某些情况下,我们在两个循环中执行早期转义。如果我们稍微做一点清理,并认识到外部循环只是在做
Array.prototype.findIndex
已经为我们做的工作,那么我们可以写一个我认为更简单的版本:我们还删除了一些局部变量:
testCharacter
、characters
和result
,而不会损害可读性。同样,我们应该能够注意到剩余的循环正在执行与
Array.prototype.some
相同的工作。我们可以清理一下然后离开:我们现在正在接近我认为的一个简单函数。但是我们可以注意到
index
在一行中定义,并且只在下一行中使用一次,因此如果我们选择,我们可以简单地将其折叠起来,并删除局部变量。同样,参数strings
仅用于定义first
和rest
;我们可以通过参数解构来实现相同的目的,并跳过这些定义。在这一点上,我们回到我的初始版本:请注意,此版本不使用
first .split ('')
,而是使用[... first]
。两者都行;两者看起来都很简单。这段代码使用s .at (i)
而不是s [i]
,因为早期版本有一个并行的commonSuffix
,而at
更容易使用。但我们可以改变这一点两个选择都可以总之,这段代码比最长的版本简单得多。重要的不是长度本身。但是简单代码的一个常见副作用是代码更短。
nvbavucw2#
我假设输入的单词被认为是原子的,不应该被分解。否则,示例输入的解决方案可以在输出中保留更多的原始字符:
然后,我还将假设这些单词由空格而不是其他字符分隔,因此第一步是将输入短语拆分为以单词为元素的数组。
问题结构
你可以把这看作是一个图形问题,其中节点是已经从每个短语中处理的单词的组合状态,或者以其他方式放置:这些短语中的当前词索引的元组。边是有向的和加权的,并且表示从一个状态进展到另一个状态的“成本”。成本包括通配符使用的每个单词的点数。如果有多个解决方案具有相同的成本,则首选通配符较少的解决方案。因此,我们可以为引入的每个通配符计算0.5的成本。
例如:如果输入中的单词都不同,则解决方案是“*”,并且该解决方案的成本是单词的总计数加上单个通配符的0.5。
另一个例子是所有输入短语完全相同,比如4次“这是一个短语”,因此该短语也将是输出。该解决方案的成本为0,因为使用通配符没有省略任何单词。
最佳搜索算法
然后在该图上执行Dijkstra算法以找到解,即结束状态,其中所有单词索引都在其相应短语的末尾。
我们可以通过关注那些不需要两个连续通配符的搜索路径来消除一些搜索路径。因此,我们应该以这样一种方式递增索引,即在使用通配符之后,更新后的索引引用的单词都是相同的。如果我们决定直接使用短语的当前单词(而不是通配符),我们应该在其他字符串中找到相同的单词(从它们的当前索引开始)。为了科普这是不可能的,或者仍然导致高成本,我们还应该考虑使用通配符跳过所有当前单词(所有索引递增1)的场景。
优先级队列
由于JavaScript没有本机优先级队列,我重用了this answer的堆实现。
实现
下面是上述算法的实现:
这个算法没有一个好的最坏情况下的时间复杂度,所以如果你给它更多更长的短语,有很多常见的单词,它会变得太慢。
4c8rllxm3#
你可以使用正则表达式来实现这一点。通过将
*
替换为(.*?)
,从输入中构建正则表达式。你需要escape the special characters: