題目
最長公共字首
https://leetcode-cn。com/problems/longest-common-prefix/
公眾號 《java程式設計手記》記錄JAVA學習日常,分享學習路上點點滴滴,從入門到放棄,歡迎關注
描述
難度:簡單
編寫一個函式來查詢字串陣列中的最長公共字首。
如果不存在公共字首,返回空字串
“”
。
示例 1:
輸入:strs = [“flower”,“flow”,“flight”] 輸出:“fl”
示例 2:
輸入:strs = [“dog”,“racecar”,“car”] 輸出:“” 解釋:輸入不存在公共字首。
提示:
0 <= strs。length <= 200 0 <= strs[i]。length <= 200 strs[i] 僅由小寫英文字母組成
Solution
正常解法
解題思路
如何求最長公共字首
字串陣列中求出
最長公共字首
,這句話就意味著每個字串都必須包含這個
公共字首字串
我們可以任意指定一個字串陣列中的一個字串
PRE
以
PRE
為例子,迴圈遍歷每個字串
STR
如果
STR
中不包含
PRE
,則
PRE
字串整體長度切割減一,直到當前
STR
字串中包含
PRE
字串然後進行下一個字串的匹配,在下一個字串中同理,判斷是否包含
PRE
字串,不包含則
PRE
字串整體長度切割減一依次迴圈,最後返回
PRE
的值,也就是公共長度的值
CODE
class Solution { public String longestCommonPrefix(String[] strs) { //邊界條件判斷 if (strs == null || strs。length == 0){ return “”; } //預設第一個字串是他們的公共字首 String pre = strs[0]; //遍歷每個字串 for(String str : strs){ //死迴圈判斷當前STR是否包含PRE,直到包含則跳出while迴圈 while(str。indexOf(pre)!=0){ //不包含則切割最後一位 pre = pre。substring(0, pre。length() - 1); } } return pre; } }
複雜度
時間複雜度:
O(mn)
,其中
m
是字串陣列中的字串的平均長度,
n
是字串的數量。最壞情況下,字串陣列中的每個字串的每個字元都會被比較一次。
空間複雜度:
O(1)
,使用的額外空間複雜度為常數。
結果
執行用時:
4
ms, 在所有
Java
提交中擊敗了
100。00
%的使用者
記憶體消耗:
38。5
MB, 在所有
Java
提交中擊敗了
72。23
%的使用者
LeetCode名句
這題屬於簡單嗎???