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的中间段啊
|
