所以昨晚我解决了这个LeetCode问题。我的解决方案不是很好，很慢。因此，我试图计算我的算法的复杂性，以与LeetCode在解决方案部分列出的标准算法进行比较。这是我的解决方案:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# Get lengths of all strings in the list and get the minimum
# since common prefix can't be longer than the shortest string.
# Catch ValueError if list is empty
try:
min_len = min(len(i) for i in strs)
except ValueError:
return ''
# split strings into sets character-wise
foo = [set(list(zip(*strs))[k]) for k in range(min_len)]
# Now go through the resulting list and check whether resulting sets have length of 1
# If true then add those characters to the prefix list. Break as soon as encounter
# a set of length > 1.
prefix = []
for i in foo:
if len(i) == 1:
x, = i
prefix.append(x)
else:
break
common_prefix = ''.join(prefix)
return common_prefix
我有点纠结于计算复杂性。第一步——获取字符串的最小长度——需要O(n)，其中n是列表中字符串的个数。最后一步也很简单——它需要O(m)，其中m是最短字符串的长度。
但是中间的部分令人困惑。set(list(zip(*strs)))应该再取O(m)然后再做n次，所以是O(mn)但总体复杂度是0 (mn + m + n)，这对于解决方案的速度来说似乎太低了。
另一个选择是中间步骤是O(m^2*n)，这更有意义。计算复杂度的正确方法是什么?
是的，中间部分是O{mn}，整体是O{mn}，因为m和n的大值使O{m}和O{n}项相形见绌。
您的解决方案具有理想的运行时复杂度顺序。
优化:短路
然而，你可能会对其他人有更快的解决方案感到沮丧。我怀疑其他可能在第一个不匹配的索引上短路。
让我们考虑一个包含26个字符串(['a'*500, 'b'*500, 'c'*500, ...])的测试用例。您的解决方案将继续创建一个500长的列表，每个条目包含一组26个元素。同时，如果短路，则只处理第一个索引，即一组26个字符。
尝试将list更改为generator。这可能是所有你需要短路。
foo = (set(x) for x in zip(*strs)))
您可以跳过min_len检查，因为zip的默认行为是只迭代最短的输入。
优化:生成中间结果
我看到你将每个字母附加到一个列表中，然后是''.join(lst)。这是有效的，特别是与迭代地追加字符串的替代方法相比。
然而，我们可以很容易地保存计数器match_len。然后，当我们检测到第一个不匹配时，只需:
return strs[0][:match_len]