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

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:
All given inputs are in lowercase letters a-z.

簡(jiǎn)單的說就是求最長(zhǎng)公共前綴，解法的思路如圖，

image-20180708134936170

就是每?jī)蓚€(gè)字符串進(jìn)行對(duì)比，尋找最大的前綴，然后找到的前綴與下一個(gè)字符串進(jìn)行前綴匹配，當(dāng)然也可以先把字符串根據(jù)長(zhǎng)度排序，用最短的那個(gè)字符串作為最開始的前綴來進(jìn)行匹配查找，因?yàn)樽铋L(zhǎng)公共前綴的長(zhǎng)度不會(huì)超過最短的字符串長(zhǎng)度~

Solution

package main

import (
    "fmt"
    "strings"
)

func longestCommonPrefix(strs []string) string {
    // 如果數(shù)組是空的，那么返回 ""
    if(len(strs) == 0) {
        return ""
    }
    // 取第一個(gè)字符串作為初始的前綴
    prefix := strs[0]
    for i := 1; i < len(strs); i++{
        // 這個(gè)循環(huán)的目的是，根據(jù)查找前綴的位置來判斷是否已經(jīng)找到公共前綴
        for ; strings.Index(strs[i], prefix) != 0; {
            // 沒找到，則去掉最后一位，繼續(xù)嘗試
            prefix = prefix[0:len(prefix) - 1]
            // 如果沒有公共前綴，就返回 ""
            if(len(prefix) == 0) {
                return ""
            }
        }
    }
    return prefix
}

func main() {
    a := []string{"flower", "flow", "flight"}
    fmt.Println(longestCommonPrefix(a))
    a = []string{"aa", "a"}
    fmt.Println(longestCommonPrefix(a))
}