Longest Common Prefix_LeetCode

全栈程序员站长

发布于 2022-08-23 14:34:07

2320

发布于 2022-08-23 14:34:07

大家好，又见面了，我是你们的朋友全栈君。

1.思路：求strs数组的长度，当len==0，len==1分开考虑；i从1-min_len，以strs[0][i]作为对照，一旦出现strs[j][i]!=strs[0][i]，结束循环，则输出之前判断好了的字符串。

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        #判断list长度
        len_strs=len(strs)
        if len_strs==1:
            return strs[0]
        if len_strs==0:
            return ""
        min_len=self.min_length_strs(strs)
        result=""
        for i in range(min_len):
            temp=strs[0][i]
            for j in range(1,len_strs):
                if temp!=strs[j][i]:
                    return result
            result = result + temp
        return result

    def min_length_strs(self,strs):
        min_len = 999999
        for i in range(len(strs)):
            if len(strs[i])<min_len:
                min_len=len(strs[i])
        return min_len

2.查看了一下网上的资料，觉得不错

https://www.jianshu.com/p/63dcc0d7db75 提到横向遍历，纵向遍历，分治法和二分法的思想。

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

int indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。

在理解这个的时候查阅了strs[i].indexOf(prefix)!=0，java中的indexOf(str)要么返回-1，要么返回对应的下标值。这里判断是否等于0，等于0，则prefix应该是一个字符，可以直接去判断下一个元素的以一个字符是不是与前面的相同。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/138501.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年5月6，如有侵权请联系 cloudcommunity@tencent.com 删除

java