ninehills / blog

https://ninehills.tech
862 stars 80 forks source link

LeetCode-14. Longest Common Prefix #21

Closed ninehills closed 7 years ago

ninehills commented 7 years ago

问题

https://leetcode.com/problems/longest-common-prefix/#/description

Write a function to find the longest common prefix string amongst an array of strings.

思路

两两对比找出最长的prefix字符串,然后顺序对比下去

解答

package main

import "fmt"

// ----------------------
func longestCommonPrefix(strs []string) string {
    common_prefix := ""
    for index, str := range strs {
        if index == 0 {
            common_prefix = str
            continue
        }
        common_prefix = getCommonPrefix(common_prefix, str)
    }
    return common_prefix
}

func getCommonPrefix(a string, b string) string {
    //fmt.Println(a, b)
    b_length := len(b)
    for index, char := range a {
        if index < b_length {
            //fmt.Println(index, byte(char), b[index])
            if byte(char) == b[index] {
                continue
            } else {
                return a[:index]
            }
        } else {
            return b
        }
    }
    return a
}

// ----------------------

func main() {
    var strs = []string{"MMMCMLXXXIX", "MMMCsd", "MMIDFSDF"}
    fmt.Println(longestCommonPrefix(strs))
    strs = []string{"", "b"}
    fmt.Println(longestCommonPrefix(strs))
    strs = []string{"b", "b"}
    fmt.Println(longestCommonPrefix(strs))
}