最长公共前缀

2019-07-13  本文已影响0人  hustyanye

https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1014/

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

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

示例 1:

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

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

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

思路很简单,取出第一个串,往后比较其他的字符串,遇到有字符不同的,就break掉,最后算下最长的前缀就好了。需要注意的是,取其他字符串的字符时,需要先判断下其他字符串是否存在以及长度是否达到遍历的长度。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs :
            return ''
        if len(strs)==1:
            return strs[0]
        
        first_str = strs[0]
        common_prefix_len = -1
        for i in range(0,len(first_str)):
            
            is_common_alpha = True
            for j in range(1,len(strs)):
                tmp_str = strs[j]
                if tmp_str and len(tmp_str)>i and first_str[i] == tmp_str[i]:
                    continue
                else:
                    is_common_alpha = False
                    break
            if is_common_alpha:
                common_prefix_len = i
            else:
                break
        if common_prefix_len >= 0:
            return first_str[0:common_prefix_len+1]
        else:
            return ''
                    
上一篇下一篇

猜你喜欢

热点阅读