编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空 字符串 。 输入:strs = [flower,flow,flight] 输出:fl 要求:时间复杂度 O(mn),空间复杂度 O(1)

可以使用纵向扫描的方法来找到最长公共前缀。

具体做法是，从字符串数组的第一个字符串开始，依次遍历每个字符，同时比较其它字符串的相同位置是否也为该字符，如果不是，则当前位置之前的字符串即为最长公共前缀。

代码实现如下：

def longestCommonPrefix(strs: List[str]) -> str:
    if not strs:
        return ""
    for i in range(len(strs[0])):
        c = strs[0][i]
        for j in range(1, len(strs)):
            if i == len(strs[j]) or strs[j][i] != c:
                return strs[0][:i]
    return strs[0]

时间复杂度为 $O(mn)$，空间复杂度为 $O(1)$。

相关问题

js编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串

好的，以下是实现最长公共前缀的 JavaScript 函数：

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, prefix.length - 1);
      if (prefix.length === 0) return "";
    }
  }
  return prefix;
}

这个函数接收一个字符串数组 `strs` 作为参数，返回这个数组中所有字符串的最长公共前缀。首先判断数组是否为空，如果是，则返回空字符串。然后将第一个字符串设置为前缀 `prefix`。接下来循环遍历数组中的所有字符串，如果当前字符串不以 `prefix` 开头，则将 `prefix` 不断缩短，直到当前字符串以 `prefix` 开头或者 `prefix` 变成空字符串，如果 `prefix` 变成了空字符串，则说明不存在公共前缀，返回空字符串。最后返回 `prefix`。

JAVA编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。示例 1： 输入：strs = ["flower","flow","flight"] 输出："fl" 示例 2：

输入：strs = ["dog","racecar","car"] 输出：""

我可以回答这个问题。以下是一个JAVA函数来查找字符串数组中的最长公共前缀：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }

    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
        }
    }
    return prefix;
}

这个函数的基本思想是，我们首先假设第一个字符串是最长公共前缀，然后将其与接下来的字符串逐个比较，找出它们之间的公共前缀，并更新最长公共前缀。如果查找过程中出现空字符串或者不存在公共前缀，就直接返回空字符串。