文章目錄

• • • 題目描述
    • 我的解法
    • 反思1
    • 優(yōu)化1
    • 反思2
    • 優(yōu)化2
    • 其他思路
    • 總結(jié)
    • Github

題目描述

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 “”。

示例 1:

輸入: [“flower”,“flow”,“flight”]
輸出: “fl”

示例 2:

輸入: [“dog”,“racecar”,“car”]
輸出: “”

解釋: 輸入不存在公共前綴。
說明:

所有輸入只包含小寫字母 a-z 。

---

我的解法

public String longestCommonPrefix(String[] strs) {//特殊情況if(null == strs||0 == strs.length)//字符數(shù)組為空的情況return "";if(1 == strs.length)//數(shù)組中只有一個(gè)字符串，那么前綴就是他本身return strs[0];boolean finalRound = false;boolean isPlusIndex = true;int index = 0;while(!finalRound){for(int i=1; i<strs.length; i++){if(index > strs[i-1].length() ||index > strs[i].length()){//如果超出某個(gè)字符串長度了，終止//這個(gè)也同時(shí)校驗(yàn)了某一個(gè)字符串為空的情況finalRound = true;isPlusIndex = false;break;}if(strs[i-1].substring(0,index).equals(strs[i].substring(0,index))) {} else{//如果前綴不相等了，終止finalRound = true;isPlusIndex = false;break;}}if(isPlusIndex)index++;}return strs[0].substring(0,index-1);//因?yàn)槲野炎铋_始假設(shè)多了一位“”，所以實(shí)際的索引要減去一}

用間：9ms
戰(zhàn)勝：77.55%

---

反思1

其實(shí)可以單拿出數(shù)組中第一個(gè)字符串作為標(biāo)準(zhǔn)，讓其與之后的字符串進(jìn)行比較。如果有相同前綴，第一個(gè)字符串必然也有。若前綴不同則可以直接return “”。

我們在拿第一個(gè)字符串為標(biāo)準(zhǔn)比較前綴的時(shí)候。舉個(gè)例子，比如第一個(gè)字符串和第二字符串前5位都是一致的，但是在跟第三個(gè)字符串比較的時(shí)候只有前三位一致。也就是說，我們的前綴字節(jié)數(shù)應(yīng)該是隨著遍歷的深度越來越少。這樣如果我們還是從字符串的第一個(gè)字節(jié)開始比較的話，很大幾率我們的前幾位字符都是一樣的，這樣就浪費(fèi)了一些時(shí)間。相反我們從字符串的末位字符開始比較，則很快能篩掉不一致的字符。

---

優(yōu)化1

public String longestCommonPrefix3(String[] strs) {if(strs.length == 0) return "";String prefix = strs[0];for (int i = 0; i <= strs.length - 1; i++){while(!strs[i].startsWith(prefix)){prefix = prefix.substring(0,prefix.length()-1);}}return prefix;}

用時(shí)：9ms
戰(zhàn)勝：77.55%
==! 在我的電腦上并沒有看出太大的差距

---

反思2

首先我們拿第一個(gè)字符串作為標(biāo)準(zhǔn)，就沒有必要再讓他跟自己比較了

如果發(fā)現(xiàn)沒有公共前綴，直接跳出循環(huán)，減少系統(tǒng)開銷

---

優(yōu)化2

public String longestCommonPrefix4(String[] strs) {if(strs.length == 0 || strs[0].length() == 0) return "";String prefix = strs[0];for (int i = 1; i <= strs.length - 1; i++){if(!"".equals(prefix)){while(!strs[i].startsWith(prefix)){prefix = prefix.substring(0,prefix.length()-1);}}}return prefix;}

用時(shí)：6ms
戰(zhàn)勝：98.61%

---

其他思路

我比較喜歡這優(yōu)化的版本，雖然leetcode上有更快的版本（并沒有覺得有什么可圈可點(diǎn)的地方，跑出了4ms估計(jì)是網(wǎng)絡(luò)電腦的原因，我本機(jī)還是跑了9ms）。但是少量的代碼更加意味著思路的清晰。有時(shí)候這才是更重要的。

---

總結(jié)

有的時(shí)候找前面相似的問題，從末位排除是更好的辦法。

---

Github

LeetCode刷題筆記

總結(jié)

以上是生活随笔為你收集整理的LeetCode-14 最长公共前缀的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。