14. 最长公共前缀

一、题目原型：

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

二、题目意思剖析：

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

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

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

三、解题思路：

题目意思比较简单，首先我们需要找到最短的那个字符串，因为要找的公共串那个最短的字符串一定是包含的，我们需要的是最短字符串的长度minString。
我们需要一个变量maxLenth，表示最大长度。
我们先取到数组中第一个元素的prefix，然后和之后的元素的prefix进行比对。
例子：[“flower”,”flow”,”flight”]
第一轮：maxLenth = 0，prefix = f，第0个元素prefix和后面的都相同，maxLenth + 1
第二轮：maxLenth = 1，prefix = fl，第0个元素prefix和后面的都相同，maxLenth + 1
第三轮：maxLenth = 2，prefix = flo，第0个元素prefix和第2个元素不同(fli)，直接break

func longestCommonPrefix(_ strs: [String]) -> String {
    var minString: String = ""
    if strs.count > 0 {
       minString = strs.min()!
    }
    var maxLenth: Int = 0
    var prefix: String = ""
    var tempIndex: Int = 0
    for _ in 0..<minString.count {
        prefix = String(strs[0].prefix(maxLenth+1))
        for j in 1..<strs.count{
            if prefix == String(strs[j].prefix(maxLenth+1)) {
                tempIndex = tempIndex + 1
                if tempIndex == strs.count - 1 {
                    maxLenth = maxLenth + 1
                    tempIndex = 0
                }
            }
            else {
                tempIndex = 0
                break
            }
        }
    }
    if strs.count == 1 {
        return strs[0]
    }else {
        if maxLenth == 0 {
            return ""
        }else {
            return String(strs[0].prefix(maxLenth))
        }
    }
}

// 简化代码方案
思路：取到数组里的第0个元素，然后把它扔进取strs里遍历，从1开始。如果发现strs的其他元素不包含第0个元素，就让第0个元素长度-1。

func longestCommonPrefix(_ strs: [String]) -> String {
    guard var prefix = strs.first else {
        return ""
    }
    for i in 1..<strs.count {
        // 如果strs里不包括第0个元素，就让他的长度-1
        while(!strs[i].hasPrefix(prefix)) {
            // 关键两句代码
            prefix = String(prefix.prefix(prefix.count-1))
            if (prefix.count == 0) {
                return ""
            }
        }
    }
    return prefix
}

四、小结

耗时20毫秒，超过96.51%的提交记录，总提交数118。