七爪源码：LeetCode—14：最长公共前缀（有图像的解决方案）

大荆

问题：
编写一个函数来查找字符串数组中最长的公共前缀字符串。
如果没有公共前缀，则返回一个空字符串“”。

示例 1：
Input: strs = ["flower","flow","flight"]Output: "fl"示例 2：
Input: strs = ["dog","racecar","car"]Output: ""Explanation: There is no common prefix among the input strings.约束：

• 1 <= strs.length <= 200
  
• 0 <= strs.length <= 200
  
• strs 仅由小写英文字母组成。
  

解决方案：
在这里，我们可以使用简单的解决方案：

• 首先，我们将找到最短的字符串及其长度。
  
• 其次，我们将取最短的字符串并将其每个字符与所有其他字符串一一匹配。
  
• 一旦遇到不匹配的字符，我们就会跳出循环。
  

让我们通过图像来理解它：
假设我们给出了一个数组，它在下面

现在我们将应用我们的第一个条件：在给定的数组中找到最短的字符串。

我们将得到 AND。 现在检查它的长度：它是 3，所以我们将创建长度为 3 的 for 循环并逐个比较字符。

现在根据第二个条件，我们正在尝试一个一个匹配字符。 所以对于第一次迭代。

首先，我们将获取第一个元素的第一个索引值“A”并将其存储在当前变量中，

根据第三个条件，我们正在检查当前变量的值和每个其他元素的第一个索引值，如果都匹配，那么我们将进入下一个循环，否则我们将终止这个循环。
这里当前字符“A”与其他元素的第一个索引值匹配。 所以首先我们将匹配的字符存储到“结果”变量中。

现在我们取第一个元素的第二个索引 (first_element[1]) 值，即“B”

在上面，“B”也在数组的每个其他元素中匹配，所以我们将 B 也附加到“result”变量中，“result”将是“AB”。
现在我们取第一个元素的第三个索引 (first_element[2]) 值，即“C”

在这里，'C' 并非在字符串的每个元素中都可用，因此我们不会将“C”附加到“result”变量中。

因此，根据第三个条件，我们在此处终止 for 循环并返回变量“result”，即“AB”，这将是我们的答案。


代码（Java）：
class Solution {    public String longestCommonPrefix(String[] strs) {         // Longest result string        StringBuilder resultString = new StringBuilder();        // Base condition        if (strs == null || strs.length == 0) {            return resultString.toString();        }        // If only one element, then return that element        if (strs.length == 1) {            return strs[0];        }        // Find the minimum length string from the array        int minimumLength = strs[0].length();        for (int i = 1; i < strs.length; i++) {            minimumLength = Math.min(minimumLength, strs.length());        }        // Loop for the minimum length        for (int i = 0; i < minimumLength; i++) {            // Get the current character from first string            char current = strs[0].charAt(i);            // Check if this character is found in all other strings or not            for (String str : strs) {                if (str.charAt(i) != current) {                    return resultString.toString();                }            }            resultString.append(current);        }        return resultString.toString();    }}代码（Python）：
class Solution(object):    def longestCommonPrefix(self, strs):        """        :type strs: List[str]        :rtype: str        """        # Longest common prefix string        result = ""        # Base condition        if strs is None or len(strs) == 0:            return result        # If there is only one element in array then return it        if len(strs) == 1:            return strs[0]        # Find the minimum length string from the array        minimum_length = len(strs[0])        for i in range(1, len(strs)):            minimum_length = min(minimum_length, len(strs))        # Loop until the minimum length        for i in range(0, minimum_length):            # Get the current character from the first string            current = strs[0]            # Check if this character is found in all other strings or not            for j in range(0, len(strs)):                if strs[j] != current:                    return result            result += current        return result

时间复杂度：
如果 n 是数组的长度，m 是最短字符串的长度，则最坏情况的时间复杂度将为 O(m × n)。


空间复杂度：
由于我们没有使用任何内部数据结构进行中间计算，空间复杂度将为 O(1)。


感谢阅读这篇文章
如果我做错了什么？ 让我在评论中。 我很想改进。


关注七爪网，获取更多APP/小程序/网站源码资源！

原文地址：https://m.toutiao.com/i7124681667222045188/

荆七针

javascript中最长的公共前缀字符串