w***y 发帖数: 6251 | 1 考古pinterest面经,看到两个类似的题目
这个在glassdoor看到的:给一组words,找longest common substring
英文原文:given an array of words find what is and how long is the length of
the longest common substring between two words in the array
这个在本版看到的:
"给一组字符串,找最长的公共前缀,至少两个字符串公共"
这个给了解法,没看懂5555
[hash all prefixes of one string and then scan through
def longest_common_prefix(strings):
first = strings[0]
l = len(first)
prefixes = set([first[:i] for i in range(l+1)])
for s in strings[1:]:
l = min(l, len(s))
while s[:l] in prefixes:
l -= 1
return first[:l]
求高手指点一下,我好像只能想明白两两组合的暴力解法//汗 |
l*k 发帖数: 10 | 2 这个就是保存了第一个string的所有prefix,然后从第二个string开始,每次只需要比
较前面比较过的strings的最长共同prefix。 |
d*****c 发帖数: 605 | |
w***y 发帖数: 6251 | 4 sorry 可能一开始没说清楚,我知道DP怎么做 longest common substring
这种是一个array of strings,longest common substring between two words in
the array, 除了两两组合找LCS,然后在这些结果里找longest,有什么比较巧妙的方
法么?
【在 d*****c 的大作中提到】 : CLRS书上的原题,dp那章
|
w***y 发帖数: 6251 | 5 ic 明白这个思路了, 我对python不是超级熟,不过while那部分是不是
while s[:l] NOT in prefixes:
l--
但是这又回到题面,我以为是‘找最长的公共前缀,至少两个字符串公共 ’。 这个解
法我的理解是找所有string的公共前缀,对嘛?
愈发觉得自己IQ不够使了 😓
【在 l*k 的大作中提到】 : 这个就是保存了第一个string的所有prefix,然后从第二个string开始,每次只需要比 : 较前面比较过的strings的最长共同prefix。
|
d*****c 发帖数: 605 | 6 为什么是prefix呢,LCS可以是两个string的中间段啊
【在 l*k 的大作中提到】 : 这个就是保存了第一个string的所有prefix,然后从第二个string开始,每次只需要比 : 较前面比较过的strings的最长共同prefix。
|
w***y 发帖数: 6251 | 7 这是两个题目,一个是问的lcs, 一个是问的prefix
【在 d*****c 的大作中提到】 : 为什么是prefix呢,LCS可以是两个string的中间段啊
|