題目
最長公共字首
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名句
這題屬於簡單嗎？？？
