LeetCode 14 最长公共前缀

题目：

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

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

解题：

看到哪一位不相同了，前缀就是之前的那些

代码：

func longestCommonPrefix(strs []string) string {
    var str []byte
    l := len(strs)
    j := 0
    for {
        if j >= len(strs[0]) {
            break
        }
        tmp := strs[0][j]
        flag := true
        for i := 1; i < l; i++ {
            if j >= len(strs[i]) || tmp != strs[i][j] {
                flag = false
            }
        }
        if !flag {
            break
        }
        str = append(str, tmp)
        j++
    }
    return string(str)
}

官方解答1：横向扫描

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    count := len(strs)
    for i := 1; i < count; 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
}

官方解答2：纵向扫描

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]
}

官方解答3：分治

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
}

官方解答4：二分查找法

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


    isCommonPrefix := func(length int) bool {
        str0, count := strs[0][:length], len(strs)
        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]
}

我的方法算是纵向扫描了，就代码量来说还是纵向扫描最少，也最好理解