【Leetcode刷题】算法：最长公共前缀

亦凉 2023-09-27 23:38 22阅读 0赞

#### 文章目录 ####

*  一、题目描述
 *  二、解题思路
 *   *  2.1 解法1
     *  2.2 解法2
     *  2.3 解法3
     *  2.4 解法4
 *  三、结果提交

## 一、题目描述 ##

![在这里插入图片描述][f035b4a080e1497ebef5646584de70c7.png]

## 二、解题思路 ##

### 2.1 解法1 ###

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
        	if not strs:  # 如果字符串数组为空，则返回空字符串
            	return ""
    
        	min_len = min(len(s) for s in strs)  # 找到字符串数组中最短字符串的长度
        	common_prefix = ""  # 初始化公共前缀
    
        	for i in range(min_len):  # 遍历最短字符串的每个字符
            	char = strs[0][i]  # 获取第一个字符串中的当前字符
    
            	# 检查其他字符串中对应位置的字符是否与第一个字符串中的字符相同
            	if all(s[i] == char for s in strs):
                	common_prefix += char  # 如果相同，则将字符添加到公共前缀中
            	else:
                	break  # 如果有不相同的字符，则退出循环
    
        	return common_prefix

这段代码是一个查找字符串数组中最长公共前缀的函数。让我们逐行解读代码：

1.  if not strs:：如果字符串数组为空，则返回空字符串。这个条件检查数组是否为空，如果为空，则没有公共前缀可找，直接返回空字符串。
2.  min\_len = min(len(s) for s in strs)：找到字符串数组中最短字符串的长度。通过使用生成器表达式和min函数，获取字符串数组中所有字符串的长度，并返回最小值，即最短字符串的长度。
3.  common\_prefix = “”：初始化公共前缀为空字符串。
4.  for i in range(min\_len):：遍历最短字符串的每个字符的索引。
5.  char = strs\[0\]\[i\]：获取字符串数组中的第一个字符串中的当前字符。这里假设第一个字符串不为空，因为前面已经检查过数组是否为空。
6.  if all(s\[i\] == char for s in strs):：检查其他字符串中对应位置的字符是否与第一个字符串中的字符相同。通过使用生成器表达式和all函数，遍历字符串数组中的每个字符串，检查当前字符是否与第一个字符串中的字符相同。只有当所有字符串的当前字符都相同时，条件才成立。
7.  common\_prefix += char：如果相同，则将当前字符添加到公共前缀中。
8.  else:：如果有不相同的字符，则退出循环。
9.  break：退出循环，不再继续遍历后面的字符。
10. return common\_prefix：返回最长公共前缀。

该函数通过逐个比较字符的方式，找到字符串数组中的最长公共前缀，并返回结果。

### 2.2 解法2 ###

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            if not strs:
                return ""
    
            # 将字符串数组按字典序排序
            strs.sort()
            
            # 比较排序后的第一个字符串和最后一个字符串的公共前缀
            common_prefix = ""
            for i in range(len(strs[0])):
                if strs[0][i] == strs[-1][i]:
                    common_prefix += strs[0][i]
                else:
                    break
    
            return common_prefix

这个优化算法的思路是，将字符串数组按字典序排序，然后比较排序后的第一个字符串和最后一个字符串的公共前缀。因为排序后的字符串数组，第一个字符串和最后一个字符串的公共前缀一定是整个数组的公共前缀。所以只需要比较这两个字符串的公共前缀即可。

你可以将这个类方法放在类中使用，或者直接调用该函数来查找字符串数组中的最长公共前缀。

### 2.3 解法3 ###

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            if not strs:
                return ""
    
            # 找到最短的字符串长度
            min_len = min(len(s) for s in strs)
    
            # 比较每个字符位置上的字符是否相同
            common_prefix = ""
            for i in range(min_len):
                if all(s[i] == strs[0][i] for s in strs):
                    common_prefix += strs[0][i]
                else:
                    break
    
            return common_prefix

这个优化算法的思路是，在找到最短的字符串长度后，只需比较每个字符位置上的字符是否相同。通过使用 all 函数，遍历每个字符串的对应字符，只有当所有字符串的当前字符都相同时，才将该字符添加到公共前缀中。

这种优化可以减少不必要的比较操作，并在不需要排序的情况下找到最长公共前缀，进一步减少运行时的时间和内存消耗。

### 2.4 解法4 ###

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            ans = ''
            for i in list(zip(*strs)):
                if len(set(i)) == 1:
                    ans += i[0]
                else:
                    break
            return ans

1.  ans = ‘’：初始化结果字符串为空。
2.  for i in list(zip(\*strs)):：使用zip(\*strs)将字符串数组进行解压缩，将每个字符串的相同索引位置的字符组成元组。然后使用for循环遍历这些元组，即遍历字符串数组中的每个字符的相同索引位置。
3.  if len(set(i)) == 1:：检查当前位置的字符是否都相同。通过将元组转换为集合（set）并检查集合中元素的数量是否为1，来判断是否所有字符相同。
4.  ans += i\[0\]：如果当前位置的字符都相同，则将字符添加到结果字符串中。由于在这个位置上所有字符都相同，所以选择任意一个字符添加到结果字符串中都可以。
5.  else:：如果有不相同的字符，则退出循环。
6.  break：退出循环，不再继续遍历后面的位置。
7.  return ans：返回最长公共前缀。

该函数通过逐个比较字符的方式，找到字符串数组中的最长公共前缀，并返回结果。与之前的实现相比，这个代码使用了zip函数和集合来简化逻辑，并更加紧凑和高效地查找公共前缀。

## 三、结果提交 ##

![在这里插入图片描述][4968f496c7e04472996868da96000836.png]

[f035b4a080e1497ebef5646584de70c7.png]: https://img-blog.csdnimg.cn/f035b4a080e1497ebef5646584de70c7.png
[4968f496c7e04472996868da96000836.png]: https://img-blog.csdnimg.cn/4968f496c7e04472996868da96000836.png