Swift 最长公共前缀 - LeetCode

LeetCode.jpg

题目： 最长公共前缀

描述：

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

案例1：

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

案例2:

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

说明:

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

方案一：将字符串转为[Character]，第一个和第二个求最长前缀，前缀和第三个求最长前缀...

代码一：

func longestCommonPrefix(_ strs: [String]) -> String {
    
    if strs.isEmpty { return "" }
    if strs.count == 1 {
        return strs.first!
    }
    //将[String] -> [[Character]]
    var chars = strs.map{str in Array(str)}
    
    //求两个[Character] 的公共前缀
    func twoLongestCommonPrefix(_ str1: [Character], str2: [Character]) ->  [Character] {
        var index = 0
        var temp1 = [Character]()
        while index < str1.count && index < str2.count {
            if str1[index] == str2[index] {
                temp1.append(str1[index])
                index += 1
            } else {
                break
            }
        }
        return temp1
    }
    
    var temp = chars[0]
    for i in 1..<chars.count {
        if temp.isEmpty {
            break
        }
        temp = twoLongestCommonPrefix(temp, str2: chars[i])
        print(temp)
    }
    
    return String(temp)
}

执行用时:28ms

方案二：取出第一个字符串，使用后面的字符串判断第一个字符串是否是他们的前缀，不是则将第一个字符串长度减一，继续判断

代码二：

func longestCommonPrefix(_ strs: [String]) -> String {
    let count = strs.count
    
    if count == 0 {
        return ""
    }
    if count == 1 {
        return strs.first!
    }
    
    var result = strs.first!
    for i in 1..<count {
        while !strs[i].hasPrefix(result) {
            result = String(result.prefix(result.count - 1))
            if result.count == 0 {
                return ""
            }
        }
    }
    return result
}

执行用时：16ms

开始我想的是如果字符串长度是无序的，那么把字符串变为有序是可以提升效率的，所以我加了如下代码 进行排序

let s = strs.sorted{$0.count < $1.count}

但实际测试发现，效率并未提升、、、我忽略了排序的时间、、、、尴尬了

用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。