算法：最长公共前缀

本文主要是介绍算法：最长公共前缀，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 编写一个函数来查找字符串数组中的最长公共前缀。

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

示例 1:

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

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    //第一个字符串
    prefix := strs[0]
   //字符串数组的长度
    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 := 0
    for 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++ {
        //遍历字符串数组中的每个字符串
        for j := 1; j < len(strs); j++ {
            if i == len(strs[j]) || strs[j][i] != strs[0][i] {
                return strs[0][:i]
            }
        }
    }

    //以第一个字符串为基准
    return strs[0]
}

//分治
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    var lcp func(int, int) string
    lcp = 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是字符串数组的长度
        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, minLength
    for low < high {
        mid := (high - low + 1) / 2 + low
        if isCommonPrefix(mid) {
            low = mid
        } else {
            high = mid - 1
        }
    }

    return strs[0][:low]
}

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

这篇关于算法：最长公共前缀的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！