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

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

示例?1:

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

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

func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}//第一個字符串prefix := strs[0]//字符串?dāng)?shù)組的長度count := len(strs)//prefix 就是表示最長公共前綴for i := 1; i < count; i++ {//prefix和strs[i]最長公共前綴prefix = lcp(prefix, strs[i])if len(prefix) == 0 {break}}return prefix }func lcp(str1, str2 string) string {length := min(len(str1), len(str2))index := 0for index < length && str1[index] == str2[index] {index++}return str1[:index] }func min(x, y int) int {if x < y {return x}return y }//----------------------------------------------------- func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}//遍歷第一個字符串中的每個字符for i := 0; i < len(strs[0]); i++ {//遍歷字符串?dāng)?shù)組中的每個字符串for j := 1; j < len(strs); j++ {if i == len(strs[j]) || strs[j][i] != strs[0][i] {return strs[0][:i]}}}//以第一個字符串為基準(zhǔn)return strs[0] }//分治 func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}var lcp func(int, int) stringlcp = func(start, end int) string {if start == end {return strs[start]}//取中間位字符串mid := (start + end) / 2//分別取左半邊和右半邊的最長公共串lcpLeft, lcpRight := lcp(start, mid), lcp(mid + 1, end)//取較小的長度minLength := min(len(lcpLeft), len(lcpRight))//比較兩個公共串是否相等 for i := 0; i < minLength; i++ {if lcpLeft[i] != lcpRight[i] {return lcpLeft[:i]}}return lcpLeft[:minLength]}//傳入字符串兩端return lcp(0, len(strs)-1) }func min(x, y int) int {if x < y {return x}return y }//----------------------------------------------------------------------------------- //二分 func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}isCommonPrefix := func(length int) bool {str0, count := strs[0][:length], len(strs)//count是字符串?dāng)?shù)組的長度for i := 1; i < count; i++ {if strs[i][:length] != str0 {return false}}return true}//第一個字符串的長度minLength := len(strs[0])//求出最短字符串長度for _, s := range strs {if len(s) < minLength {minLength = len(s)}}low, high := 0, minLengthfor low < high {mid := (high - low + 1) / 2 + lowif isCommonPrefix(mid) {low = mid} else {high = mid - 1}}return strs[0][:low] }

參考地址：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-

總結(jié)

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

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