Longest Common Prefix
给你一个单词数组 strs。返回每个单词都以其开头的最长字符串。如果这些单词并非都以同一个字母开头，则返回空字符串 ""。一个单词也算是它自己的前缀，因此只有一个单词时，它本身就是答案。
函数
- strsstring-array
- 要比较的单词
- 返回值string
- 所有单词共有的最长前缀，或者空字符串
约束条件
1 ≤ strs.length ≤ 2001 ≤ strs[i].length ≤ 200- 每个单词只包含小写英文字母。
示例
- 输入
- strs = ["interview", "internet", "interval", "internal"]
- 输出
- "inter"
- 解释
- 这四个单词都以
inter开头。在下一个位置，interview和interval是v，而internet和internal是n，所以前缀到这里就结束了。
- 输入
- strs = ["stack", "queue", "heap"]
- 输出
- ""
- 解释
- 这些单词分别以
s、q和h开头。它们的第一个字母都不相同，所以答案为空。
- 输入
- strs = ["prefix", "pre", "prepare"]
- 输出
- "pre"
- 解释
pre是最短的单词，另外两个单词都以它开头，所以它就是完整答案。公共前缀永远不会比最短的单词更长。
进阶
假设列表保持不变，并且不断有查询词传入。如果不重新扫描列表，你要如何为每个查询找到它与列表中某个单词共享的最长前缀？
提示
逐个打开提示，每个都会多透露一点。
答案永远不会比最短的单词长。它包含的每个字母都必须满足什么条件？
只有当每个单词在位置
i都有一个字母，且这些字母都相同时，位置i处的字母才属于答案。答案在第一个不满足这一条件的位置结束。从左到右遍历第一个单词中的各个位置。在每个位置，检查其他所有单词；一旦发现某个单词太短或对应字母不同，就返回第一个单词中该位置之前的部分。
题解
只有当每个单词在同一位置都有这个字母时，它才属于答案；如果某个单词在某个位置出现不同字母或已经结束，答案就到该位置为止。这两种方法都逐字母读取单词，只是顺序不同。按列扫描会在遇到第一个不一致时停止。
逐个词缩短前缀
思路
假设第一个单词整体就是答案。把它缩短为与第二个单词共有的部分，再与第三个单词比较，依此类推。多个单词的公共前缀，就是前两个单词的公共前缀，再与第三个单词比较得到的结果：每一步都只能保留或缩短它。例如，在示例 1 中，候选前缀从 interview 缩短为 inter，然后保持不变。
每个字母最多比较一次，所以对于总共 S 个字母，时间复杂度为 O(S)。弱点在于顺序：如果有 200 个单词，每个单词 200 个字母，且只有最后一个单词的首字母不同，那么在最后一个单词将前缀缩短为空之前，你会进行近 40,000 次比较。
算法
- 将
prefixLen设为strs[0]的长度。 - 对于其他每个单词，统计它与
strs[0]开头相同的字母数，最多统计到prefixLen。 - 将
prefixLen设为该数量，如果它变为 0，就提前停止。 - 返回
strs[0]的前prefixLen个字母。
def longestCommonPrefix(strs):
first = strs[0]
prefix_len = len(first)
for word in strs[1:]:
common = 0
while common < prefix_len and common < len(word) and word[common] == first[common]:
common += 1
prefix_len = common
if prefix_len == 0:
break
return first[:prefix_len]逐列比较
思路
把这些单词当作一张表来读，一次看一列。取当前列中 strs[0] 的字母，并检查其他每个单词在该位置的字母是否相同。第一次遇到字母不同的单词，或某个单词太短而没有这一列时，答案就是 strs[0] 中截至该列之前的部分。
答案正好是所有单词字母都相同的连续列，这个循环从左侧开始遍历这些列，并在一致性被打破时停止。如果一直没有被打破，答案就是 strs[0]。
有 n 个单词，答案长度为 L 时，循环最多进行 n × (L+1) 次检查，这也就是 O(S)。如果 200 个单词中只有最后一个单词的首字母不同，那么循环会在 199 次比较后停止。
算法
- 令
first为strs[0]。 - 对于从 0 到
first的长度减 1 的每一列col，读取first[col]。 - 对于其他每个单词，如果它在
col处没有字母，或者该字母不同，就返回first的前col个字母。 - 如果每一列都匹配，就返回
first。
def longestCommonPrefix(strs):
first = strs[0]
for col in range(len(first)):
for word in strs[1:]:
if col == len(word) or word[col] != first[col]:
return first[:col]
return first
易错点和边界情况
- 读取较短单词末尾之后的位置。在
prefix、pre、prepare中，第 3 列存在于prefix中，但不存在于pre中；读取字母前先检查长度。 - 只比较第一个和最后一个单词，却没有排序。在
abc、xbd、abd中，首尾两个单词有相同的ab前缀，但xbd在第 0 列就不匹配，因此答案是空字符串。 - 没有共同前缀时返回
null或占位符。答案是空字符串。 - 忘记单个单词的前缀就是它本身：只有
algorithm时，返回algorithm。 - 每次向不可变字符串中添加一个字母。长度为 200 个字母的答案就需要复制 200 次；记录长度，只需截取第一个单词一次。
常见问题4
最长公共前缀的时间复杂度是多少？
两次扫描都在 O(S) 时间内运行，其中 S 是字母总数。除答案外，额外内存为 O(1)。对于长度为 L 的答案，按列扫描的时间也受 n × (L+1) 限制，因此如果单词在开头附近就不一致，扫描会提前停止。
你能通过对单词排序，找出最长公共前缀吗？
是的。按字母顺序排列时，首尾两个单词之间的每个单词都以它们共同的部分开头，因此只比较这两个单词就能得出答案。排序会比较大约 n log n 对单词，耗时比扫描一次更长，但代码很短。
没有公共前缀时，Longest Common Prefix 应该返回什么？
空字符串 ""。只要两个单词以不同的字母开头，就会出现这种情况，例如 stack、queue 和 heap。
横向扫描和纵向扫描，哪种更好？
两者的最坏情况相同，都是 O(S)。纵向扫描是更稳妥的选择：它会在遇到任意单词不一致的第一列时停止，而横向扫描可能会先将一个较长的前缀与多个单词进行比较，直到某个较靠后的单词使比较提前结束。
def longestCommonPrefix(strs):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
strs = ["interview", "internet", "interval", "internal"]
预期输出
"inter"