七爪源码：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) 值，即“B”
在上面，“B”也在数组的每个其他元素中匹配，所以我们将 B 也附加到“result”变量中，“result”将是“AB”。
现在我们取第一个元素的第三个索引 (first_element) 值，即“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; } // Find the minimum length string from the array int minimumLength = strs.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.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 :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 # Find the minimum length string from the array minimum_length = len(strs) 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 # Check if this character is found in all other strings or not for j in range(0, len(strs)): if strs != current: return result result += current return result
时间复杂度：
如果 n 是数组的长度，m 是最短字符串的长度，则最坏情况的时间复杂度将为 O(m × n)。
空间复杂度：
由于我们没有使用任何内部数据结构进行中间计算，空间复杂度将为 O(1)。
感谢阅读这篇文章
如果我做错了什么？ 让我在评论中。 我很想改进。
关注七爪网，获取更多APP/小程序/网站源码资源！
原文地址：https://m.toutiao.com/i7124681667222045188/ javascript中最长的公共前缀字符串
页:
[1]