给定两个字符串,查找两个字符串之间从左到右顺序相同的公共字符
示例1
string_1 = 'hcarry'
string_2 = 'sallyc'
Output - 'ay'
示例2
string_1 = 'jenny'
string_2 = 'ydjeu'
Output - 'je'
示例1的说明-
示例2的说明- 我的方法- 我使用了 这就是暴力解决方案 这方面的最佳解决方案是什么string_1
和string_2
之间的常见字符是c、a、y。但是由于^ {CD3}}在^ {< CD5> }之前出现在^ {CD4}},并且在{{CD4}}{^ string_1
和string_2
之间的共同字符是j、e、y。但是由于^ {CD11}}在^ {< CD13> }之前出现{^
Example -
string_1 = 'hcarry'
string_2 = 'sallyc'
Common_characters = c,a,y
string_1_com = cay
string_2_com = ayc
sorted, counter, enumerate
函数来获取Python中的string_1_com and string_2_com
string_1_com and string_2_com
之间找到最长的公共子序列。您将得到结果的输出李>
在我的书中,这个算法叫做字符串匹配。它在O(mn)中运行,其中m和n是单词长度。我想它也可以运行在完整的单词上,什么是最有效的将取决于预期的常用字母数量以及排序和过滤是如何执行的。我将解释它的普通字母字符串,因为这更容易
其思想是查看(m+1)*(n+1)节点的有向无环图。通过此图的每条路径(从左上到右下)表示匹配单词的唯一方式。我们希望匹配字符串,并在单词中添加空格(
-
),以便它们与最大数量的常用字母对齐。例如cay
和ayc
的结束状态将是每个节点为其表示的部分匹配存储最高数量的匹配,并且在算法结束时,结束节点将为我们提供最高数量的匹配
我们从左上角开始,在这里没有匹配的字母,所以这里有0个匹配的字母(分数0)
我们将遍历此图,并使用以前节点的数据计算每个节点的最大匹配字母数
节点连接在左侧->;右,向上->;向下和斜向左向上->;马上下来
cay
中的一个字母,并将我们到达的字母与插入ayc
中的-
匹配李>ayc
消费,并将-
插入到cay
)李>查看起始节点右侧的第一个节点,它表示匹配
这个节点(显然)只能从起始节点到达
第一行和第一列中的所有节点都将为0,因为它们都表示匹配一个或多个具有相同数量
-
的字母我们得到了图表
这就是设置,现在有趣的部分开始了
查看第一个未赋值的节点,它表示将子字符串
c
与a
进行匹配,我们想确定如何使用最多数量的匹配字母到达该节点因此,通过选择这条路径到达当前节点,我们就到达了
将
c
与-
匹配不会给出正确的匹配,因此此路径的分数为0(取自上一个节点)加0(刚刚进行的匹配c/-
的分数)。因此,对于这个路径,0+0=0这也给了我们额外的0分。这个分数是0
因为
c
和a
是不同的字母,所以这个路径也得到了0+0=0但是对于下一个节点,它看起来更好。我们仍有三个备选方案需要考虑。 备选方案1&;2总是给我们额外的0分,因为它们总是表示用
-
匹配一个字母,所以这些路径将给我们0分。让我们转到备选方案3对于我们当前的节点,对角移动意味着从
这是一场比赛强>
这意味着有一条到这个节点的路径给我们1分。我们扔掉0,保存1
对于此行的最后一个节点,我们查看了三个备选方案,并意识到我们不会获得任何新的点(新的匹配),但我们可以使用之前的1点路径到达节点:
所以这个节点的得分也是1
对所有节点执行此操作,我们将得到以下完整的图
分数增加的唯一原因是什么
所以末端节点告诉我们最大匹配是2个字母。 因为在您的案例中,您希望知道分数为2的最长路径,所以您需要跟踪每个节点的路径
此图很容易实现为矩阵(或数组数组)
我建议您作为元素使用一个
tuple
和一个score
元素和一个path
元素,在path元素中只存储对齐字母,那么最终矩阵的元素将是在一个地方我注意到
a/c
,这是因为字符串ca
和ayc
有两个不同的最大长度的子序列。在这些情况下,您需要决定要做什么,要么选择一个,要么两个都保存编辑:
下面是此解决方案的一个实现
但是。。您已经知道术语“最长公共子序列”,并且可以找到许多关于动态规划算法的描述。
Wiki link
伪码
下面是一个简单的、基于动态规划的问题实现:
相关问题 更多 >
编程相关推荐