【LeetCode Easy】014 Longest Common Prefix

BDEEFE 发布于2019-08-16 16:54 / 3198人阅读

摘要：注意要检查参数数组是否为空或循环找出数组中最短的那个单词，以这个单词为基准，两层循环嵌套，外层是遍历这个最短单词的每一个字母，内层是遍历所有单词，看其它单词这个位置的字母是否和最短单词一样，若都一样，继续向下遍历，若有不一样的，，返回当前的

Easy 014 Longest Common Prefix Description：

find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".   (注意要检查参数数组是否为空或==null)
==Example==
Input: ["flower","flow","flight"]
Output: "fl"

My Solution:

for循环找出数组中最短的那个单词，以这个单词为基准，两层for循环嵌套，外层for是遍历这个最短单词的每一个字母，内层for是遍历所有单词，看其它单词这个位置的字母是否和最短单词一样，若都一样，继续向下遍历，若有不一样的，break，返回当前的最长前缀

时间复杂度O(n²)

代码如下：

 public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    String shortest = strs[0];
    String prefix = "";
    for(int i=1; i



仍旧是先找出最短字符串，以该字符串为基准，看其它字符串是否startswith该字符串，如果有不符合的，就减去最短字符串的最后一个字母然后继续遍历其它字符串，直至所有字符串都startswith某个前缀或最短字符串被减为空串
最坏情况下时间复杂度是O((shortest.length()-1) * n)，这个最坏情况可能会好于第一种方法
这个方法的时间已经非常短了，但有一点比较疑惑的是这个方法的空间复杂度比法一要高一点（挠头
（部分）代码如下：



       while (!shortest.equals("")){
           int j = 0;
           for (; j


Fast Solution
对My Solution的法二做一个改进，不需要找出最短字符串，直接用第一个字符串为基准就可以做了

云服务器海外云主机 Common Longest prefix prefix策略

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74251.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
# Leetcode 14：Longest Common Prefix 最长公共前缀

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。公众号：爱写bug Write a function to find the longest common prefix string amongst an array of strings. If there...

Keagan 2019-07-31 10:38 评论0 收藏0
# Leetcode 14：Longest Common Prefix 最长公共前缀

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。公众号：爱写bug Write a function to find the longest common prefix string amongst an array of strings. If there...

FrancisSoung 2019-08-16 18:25 评论0 收藏0
leetcode 14 Longest Common Prefix

摘要：题目详情题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。题目详情 Write a function to find the longest common prefix string amongst an array of strings. 题目要求是，给定一个字符串的数组，我们要...

suosuopuo 2019-08-16 11:04 评论0 收藏0