題目描述

編寫一個函數來查找字符串數組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 ""。

示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

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

解決方法

橫向匹配所有字符串

取出字符串數組里任意一個字符串prefix，遍歷其余的字符串判斷prefix是否是其的前綴，不是就去掉prefix最后一個字符，直到prefix為空

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

時間復雜度：O(S)，其中S是所有字符串中所有字符的總和
空間復雜度：O(1)，只使用了恒定的額外空間

二分搜索

取最短的字符串的長度minLen作為右邊界right，因為最長公共前綴的長度不可能大于字符串數組里最短字符串的長度

判斷左半部分是否是公共前綴，是的話向右尋找更長的公共前綴，反之向左尋找公共前綴

當 左邊界left > 右邊界right 尋找結束，最長公共前綴范圍就是[0, (left + right) / 2)

public String longestCommonPrefix2(String[] strs) {if (strs == null || strs.length == 0)return "";int minLen = Integer.MAX_VALUE;for (String str : strs)minLen = Math.min(minLen, str.length());int left = 1, right = minLen;while (left <= right) {int middle = (left + right) / 2;if (isCommonPrefix(strs, middle))left = middle + 1;elseright = middle - 1;}return strs[0].substring(0, (left + right) / 2);}public boolean isCommonPrefix(String[] strs, int len) {String str1 = strs[0].substring(0, len);for (int i = 1; i < strs.length; i++) {if (!strs[i].startsWith(str1))return false;}return true;}

時間復雜度：O(S*log(n))，其中S是所有字符串中所有字符的總和。
空間復雜度：O(1)。我們只使用了恒定的額外空間。

本文首發：https://lierabbit.cn/2018/05/...

總結

以上是生活随笔為你收集整理的[LeetCode]最长公共前缀（Longest Common Prefix）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。