我有一个字符串名称的Python列表,我想从所有名称中删除一个公共子字符串。你知道吗
在阅读了这个类似的answer之后,我几乎可以使用SequenceMatcher
获得想要的结果。你知道吗
但仅当所有项都有一个公共子字符串时:
From List:
string 1 = myKey_apples
string 2 = myKey_appleses
string 3 = myKey_oranges
common substring = "myKey_"
To List:
string 1 = apples
string 2 = appleses
string 3 = oranges
不过,我有一个稍微有点嘈杂的列表,其中包含一些不符合相同命名约定的零散项。你知道吗
我想从多数中删除“最常见”的子字符串:
From List:
string 1 = myKey_apples
string 2 = myKey_appleses
string 3 = myKey_oranges
string 4 = foo
string 5 = myKey_Banannas
common substring = ""
To List:
string 1 = apples
string 2 = appleses
string 3 = oranges
string 4 = foo
string 5 = Banannas
我需要一种方法来匹配“myKey\”子字符串,这样我就可以从所有名称中删除它。你知道吗
但是当我使用SequenceMatcher
时,项“foo”导致“longest match”等于blank。你知道吗
我认为解决这个问题的唯一方法是找到“最常见的子串”。但这怎么可能实现呢?你知道吗
基本示例代码:
from difflib import SequenceMatcher
names = ["myKey_apples",
"myKey_appleses",
"myKey_oranges",
#"foo",
"myKey_Banannas"]
string2 = names[0]
for i in range(1, len(names)):
string1 = string2
string2 = names[i]
match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))
print(string1[match.a: match.a + match.size]) # -> myKey_
我会首先找到出现次数最多的起始字母。然后我会把每一个有起始字母的单词,当所有这些单词都有匹配的字母时。最后,我会删除每个起始词的前缀:
给定
names = ["myKey_apples", "myKey_appleses", "myKey_oranges", "foo", "myKey_Banannas"]
我能想到的一个
O(n^2)
解决方案是找到所有可能的子字符串,并将它们存储在字典中,并记下它们出现的次数:然后选取最大发生子串
下面是一个过于冗长的解决方案:
不用说,使用递归,这个解决方案看起来会更整洁。我想我会为你画出一个粗略的动态规划解决方案。
相关问题 更多 >
编程相关推荐