题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

  1. 输入: ["flower","flow","flight"]
  2. 输出: "fl"

示例 2:

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

说明:

所有输入只包含小写字母 a-z。

方案一

class Solution:
    def longestCommonPrefix(self, strs: [str]) -> str:
        '''为了性能考虑，采用空间换时间的算法：
        方案一
        1. 循环一次输入数组，构建出所有的前缀子串
        2. 从前缀子串中找出相同的子串

        方案二
        1. 数组中不放所有前缀子串，放的是相同的前n个字符

        下述采用方案一
        '''
        if not strs:
            return ""

        substrs = self.getSubStrs(strs[0]) # 后面的公共子串比前面的长
        for i in range(1, len(strs)):
            substrs = self.getMaxPrefix(substrs, strs[i])

        return substrs[-1]


    def getSubStrs(self, s):
        if not s:
            return [""]

        substrs = []
        for i in range(len(s) + 1):
            substrs.append(s[:i])

        return substrs


    def getMaxPrefix(self, substrs, s):
        '''从已有的前缀子串数组中匹配最长的子串并返回匹配后的子串数组
        '''
        for i in range(len(substrs) - 1, 0, -1):
            if s.startswith(substrs[i]):
                return substrs[:i + 1]

        return [""]

方案二

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

    // 将数组中第一个元素拆分成字符数组
    prefixes := strings.Split(strs[0], "")

    // 循环后面的元素
    for _, str := range strs[1:] {
        if len(prefixes) > len(str) { // 前缀切片长度大于当前 str
            prefixes = prefixes[:len(str)]
        }

        for i, c := range prefixes {
            if c != string(str[i]) {
                prefixes = prefixes[:i]
                break
            }
        }
    }

    return strings.Join(prefixes, "")
}