題目
最長(zhǎng)公共前綴
https://leetcode-cn.com/problems/longest-common-prefix/
公眾號(hào) 《java編程手記》記錄JAVA學(xué)習(xí)日常，分享學(xué)習(xí)路上點(diǎn)點(diǎn)滴滴，從入門到放棄，歡迎關(guān)注
描述
難度：簡(jiǎn)單
編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴武翎。
如果不存在公共前綴，返回空字符串 ""溶锭。
示例 1：
輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：
輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴宝恶。
提示：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 僅由小寫英文字母組成
Solution
正常解法
解題思路
如何求最長(zhǎng)公共前綴
- 字符串?dāng)?shù)組中求出
最長(zhǎng)公共前綴，這句話就意味著每個(gè)字符串都必須包含這個(gè)公共前綴字符串 - 我們可以任意指定一個(gè)字符串?dāng)?shù)組中的一個(gè)字符串
PRE - 以
PRE為例子趴捅，循環(huán)遍歷每個(gè)字符串STR- 如果
STR中不包含PRE壕鹉，則PRE字符串整體長(zhǎng)度切割減一荐糜，直到當(dāng)前STR字符串中包含PRE字符串 - 然后進(jìn)行下一個(gè)字符串的匹配，在下一個(gè)字符串中同理，判斷是否包含
PRE字符串臣疑，不包含則PRE字符串整體長(zhǎng)度切割減一 - 依次循環(huán)爸黄，最后返回
PRE的值搁凸，也就是公共長(zhǎng)度的值
- 如果
CODE
class Solution {
public String longestCommonPrefix(String[] strs) {
//邊界條件判斷
if (strs == null || strs.length == 0){
return "";
}
//默認(rèn)第一個(gè)字符串是他們的公共前綴
String pre = strs[0];
//遍歷每個(gè)字符串
for(String str : strs){
//死循環(huán)判斷當(dāng)前STR是否包含PRE萌朱，直到包含則跳出while循環(huán)
while(str.indexOf(pre)!=0){
//不包含則切割最后一位
pre = pre.substring(0, pre.length() - 1);
}
}
return pre;
}
}
復(fù)雜度
時(shí)間復(fù)雜度：
O(mn)，其中m是字符串?dāng)?shù)組中的字符串的平均長(zhǎng)度红省，n是字符串的數(shù)量额各。最壞情況下，字符串?dāng)?shù)組中的每個(gè)字符串的每個(gè)字符都會(huì)被比較一次吧恃。空間復(fù)雜度：
O(1)虾啦，使用的額外空間復(fù)雜度為常數(shù)。
結(jié)果
- 執(zhí)行用時(shí)：
4ms, 在所有Java提交中擊敗了100.00%的用戶 - 內(nèi)存消耗：
38.5MB, 在所有Java提交中擊敗了72.23%的用戶
LeetCode名句
這題屬于簡(jiǎn)單嗎？傲醉？蝇闭？
