LeetCode 最长公共前缀

最长公共前缀


题目来源:https://leetcode-cn.com/problems/longest-common-prefix/

题目


编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解题思路


方法一:思路

  1. 若字符串数组为空,或长度为 0,直接返回空字符串;
  2. 取首个字符串,与下一个字符串比较,得出两者的公共前缀;
  3. 若两者比较结果无公共前缀,直接返回空字符串。否则执行下一步;
  4. 以得出的公共前缀,再与下一个字符串比较;
  5. 重复步骤 34,得出字符串数组最长公共前缀。

方法二:思路

  1. 利用 zip() 的特性,实现字符串数组每个字符串逐列比较;
  2. 利用 set() 对该列去重,若最终剩下的字符长度为 1,则表示都相同。否则,跳出循环。
  3. 取最终逐列比较,set() 去重长度为 1 的列,组合即为最长公共前缀。若无符合要求的列,直接返回空字符串。

代码实现


方法一:代码实现

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        '''找出字符串数组最长公共前缀

        Args:
            strs: 传入待匹配的字符串数组
        
        Returns:
            返回字符串数组中存在的最长公共前缀
            不存在则返回空字符串 ""
        '''
        # 若列表为空,直接返回空字符
        if not strs:
            return ""
        # 取首位字符串,以待与后面进行比较
        prefix = strs[0]
        # 遍历字符串数组,逐个比较
        for i in range(1, len(strs)):
            # 比较两字符串,找到公共前缀前,逐个比较
            while strs[i].find(prefix) != 0:
                # 未找到公共前缀前,从末尾逐个删减
                prefix = prefix[0:len(prefix)-1]
                # 若无公共前缀,直接返回
                if len(prefix) == 0:
                    return ""
        return prefix

方法二:代码实现

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        '''找出字符串数组最长公共前缀

        Args:
            strs: 传入待匹配的字符串数组
        
        Returns:
            返回字符串数组中存在的最长公共前缀
            不存在则返回空字符串 ""
        '''
        # 利用 zip() 函数的特性,逐列比较字符串数组中的每个字符串
        prefix_len = []  # 用以保存共同字符的长度
        for num,s in enumerate(zip(*strs)):
            # 利用 set() 去重复
            # 若只保留 1 个字符,则表示该列相同
            # 否则该列不同,直接跳出
            if len(set(s)) == 1:
                prefix_len.append(num)
            else:
                break
        # 如果 prefix_len 为空直接返回空字符串
        # 否则截取任意字符串的 prefix_len 列表长度的字符,即为最长公共前缀
        return strs[0][:len(prefix_len)] if prefix_len else ""

实现效果


方法一:实现效果

方法二:实现效果


以上就是本篇的主要内容


欢迎关注微信公众号《书集所录》

你可能感兴趣的