前文合集
每日一道 LeetCode 前文合集
代碼倉庫
GitHub： https://github.com/meteor1993/LeetCode
Gitee： https://gitee.com/inwsy/LeetCode
題目：最長公共字首
題目來源：https://leetcode-cn.com/problems/longest-common-prefix/
編寫一個函數來查找字元串數組中的最長公共字首。
如果不存在公共字首，傳回空字元串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共字首。
說明:
所有輸入隻包含小寫字母 a-z 。
解題思路 A ：「暴力橫向查找」
看到這道題，我又感覺我行了，先聊聊我沒看答案之前的思路，這個思路我覺得是一個正常人，看到這道題應該有的，如果這個思路都沒有，可能你比較适合學文科。
我的思路一般都很暴力，直接循環這個字元串數組，從第一個開始，挨個向後比較，比較兩個字元串的每一個字元，遇到不一樣的直接傳回。
這思路夠簡單、暴力、直接吧，我想大家第一反應應該都能想得到這個方案。
接下來是代碼時間：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
prefix = compareTwoStrs(prefix, strs[i]);
if (prefix.length() == 0) break;
}
return prefix;
}
// 擷取兩個字元串的公共字首
private String compareTwoStrs(String str1, String str2) {
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++;
}
return str1.substring(0, index);
}
我在 LeetCode 上運作了一下，直接得到這個結果，這個結果應該是我做 LeetCode 最好的結果了，竟然耗時小于 1ms ，難道我已經這麼牛皮了麼，我感覺自己飄了。
我滿懷信心的打開了答案頁，正準備寫個回答裝個 B 的時候，我傻眼了， NM ，這道題竟然有這麼多種解法的啊，心态崩了啊。
忽然想到，剛才我的方案隻是一個最簡單的正向暴力破解的方案，但是我的解法耗時低于 1ms 啊，這麼看來，我的解法還是可以的嘛。
解題思路 B ：「暴力縱向查找」
我看到答案上把我上面的那種思路叫做「暴力橫向查找」，然後大神們按照這個思路，又搞出來了「暴力縱向查找」。
圖我就不畫了，反正和上面的思路一緻，就是把橫向比較換成了縱向比較，然後一個接一個比一圈，直到最短的字元串長度結束，或者開始出現不一樣的字元為止。
代碼漲這個樣子：
public String longestCommonPrefix_1(String[] strs) {
if (strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
for (int j = 1; j < strs.length; j++) {
if (i == strs[j].length() || strs[j].charAt(i) != strs[0].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
解題思路 C ：「分治」
當我以為到這裡就結束了的時候，我接着往下翻了翻答案，結果發現我自己還是圖樣圖森破啊，我太小看了「學霸」和「大神」這兩個詞。
「分治」這個方案是先把字元串數組從中間切開，然後再按照「暴力橫向查找」的方案分别取到切開後的兩個數組的最長字首，最後再從這兩個字首中取交集。
這種方案可以看做是「暴力橫向查找」方案的一個變種方案，示意圖如下：
public String longestCommonPrefix_2(String[] strs) {
if (strs.length == 0) {
return "";
} else {
return longestCommonPrefix(strs, 0, strs.length - 1);
}
}
public String longestCommonPrefix(String[] strs, int start, int end) {
if (start == end) {
return strs[start];
} else {
int mid = (end - start) / 2 + start;
String lcpLeft = longestCommonPrefix(strs, start, mid);
String lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
}
public String commonPrefix(String lcpLeft, String lcpRight) {
int minLength = Math.min(lcpLeft.length(), lcpRight.length());
for (int i = 0; i < minLength; i++) {
if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
return lcpLeft.substring(0, i);
}
}
return lcpLeft.substring(0, minLength);
}
當然，這種方案還可以接着變種，把「暴力橫向查找」替換成「暴力縱向查找」。
解題思路 D ：「二分查找」
最後還有一種二分查找比較新奇，我覺得刷題少的人肯定想不到這種方案。
這種方案的思路是在字元串數組中，最長公共字首的長度肯定不會超過字元串數組中的最短字元串的長度（如果超過了，也不會是最長公共字首）。
首先找到最短的字元串長度 minLength ，然後随機找一個字元串判斷這個 minLength 是否是最長公共字首，如果不是則把這個 minLength 從中間劈開，接着判斷前一半是不是公共字首，如果是，則最長公共字首一定大于等于這一半，如果不是，則最長公共字首一定小于這一半，就這樣逐漸縮小範圍，直到找到為止。
這個我就不畫圖了，就是一個單純的二分法不停的往下切，直到切中了為止。
public String longestCommonPrefix_3(String[] strs) {
if (strs.length == 0) return "";
// 先擷取最小長度
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
// 定義變量，開始二分法
int low = 0, high = minLength;
while (low < high) {
// 擷取中間點
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, low);
}
public Boolean isCommonPrefix(String[] strs, int length) {
// 先擷取前一半要比較的字元串
String str0 = strs[0].substring(0, length);
for (int i = 1; i < strs.length; i++) {
for (int j = 0; j < length; j++) {
// 按字元進行判斷，如果有不一樣的字元直接傳回 false
if (str0.charAt(j) != strs[i].charAt(j)) {
return false;
}
}
}
return true;
}
從上面的結果看下來，好像是二分法的速度是最慢的，實際上這是由于測試的資料集的關系，測試所使用的的資料集可能都比較适合「暴力橫向查找」這個方案。
掃描二維碼關注「極客挖掘機」公衆号！作者：極客挖掘機
定期發表作者的思考：技術、産品、營運、自我提升等。
本文版權歸作者極客挖掘機和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果您覺得作者的文章對您有幫助，就來作者個人小站逛逛吧：
極客挖掘機