【LeetCode Easy】014 Longest Common Prefix

BDEEFE 發布于2019-08-16 16:54 / 3300人閱讀

摘要：注意要檢查參數數組是否為空或循環找出數組中最短的那個單詞，以這個單詞為基準，兩層循環嵌套，外層是遍歷這個最短單詞的每一個字母，內層是遍歷所有單詞，看其它單詞這個位置的字母是否和最短單詞一樣，若都一樣，繼續向下遍歷，若有不一樣的，，返回當前的

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(n2)

代碼如下：

 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的法二做一個改進，不需要找出最短字符串，直接用第一個字符串為基準就可以做了

GPU云服務器云服務器 Common Longest prefix prefix策略

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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