描述：编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串""
注：所有输入只包含小写字母a-z
例1：输入：["flower","flow","flight"]
输出："fl"
例2：输入：["dog", "racecar","car"]
输出：""
解释：输入不存在公共前缀
一、水平扫描法
1、横向扫描
思路：两两字符串对比，找出公共前缀，在将公共前缀和第三个字符串对比...以此类推，最后得到的公共前缀为数组的最长公共前缀
时间复杂度：O(n)，n为所有字符串中字符数量的总和
具体实现：
func longestCommonPrefix(_ strs: [String]) -> String { if strs.count == 0 { return "" } var longPrefix : String = strs[0] for i in 1..<strs.count { let new = strs[i] //两两字符串对比得到的公共前缀 var common : String = "" let count = strs[i].count > longPrefix.count ? longPrefix.count : strs[i].count var j = 0 //针对数组第二个字符串开始的遍历，用for和while都可以 // for j in 0..<count{ while j < count{ if new[new.index(new.startIndex, offsetBy: j)]==longPrefix[longPrefix.index(longPrefix.startIndex, offsetBy: j)]{ common += String(longPrefix[longPrefix.index(longPrefix.startIndex, offsetBy: j)]) }else{ break } j = j+1 } longPrefix = common } return longPrefix }
2、纵向扫描
思路：从前往后遍历字符串的每一列，先比较每个字符串相同列上的字符 即 不同字符串相同下标的字符，然后再进行对比下一列，在对比时，如果满足第一个字符的下标等于任意一个字符串的长度 或者 遍历另一个字符串相同下标的字符不同时 任一条件时，返回公共前缀
时间复杂度：O(n)，n为所有字符串中字符数量的总和
具体实现：
func longestCommonPrefix(_ strs: [String]) -> String { if strs.count == 0 { return "" } var first = strs[0] for i in 0..<first.count { let c = first[first.index(first.startIndex, offsetBy: i)] for j in 1..<strs.count { let other = strs[j] //如果满足第一个字符串的下标等于另一个字符串的个数/遍历另一个字符串的i下标字符不等于第一个i下标的字符时，说明后续字符不相等，返回0～i的字符前缀 if (i==other.count) || (other[other.index(other.startIndex, offsetBy: i)] != c){ return (first as! NSString).substring(with: NSRange.init(location: 0, length: i)) } } } return first }
二、分治法
思路：将字符串数组拆分为左右两个子数组，分别比较左右两个数组中的字符串，直到不能匹配为止
时间复杂度：O(n)，n为所有字符串中字符数量的总和
具体实现：
func longestCommonPrefix(_ strs: [String]) -> String { if strs.count == 0 { return "" } return self.longestCommonPrefix(strs, 0, strs.count-1) } func longestCommonPrefix(_ strs: [String], _ left : Int, _ right : Int) -> String { if left==right { return strs[left] } else { let mid = (left+right)/2 let lcpLeft = longestCommonPrefix(strs, left, mid) let lcpRight = longestCommonPrefix(strs, mid+1, right) return self.commonPrefix(lcpLeft, lcpRight) } } func commonPrefix(_ left : String, _ right : String)->String { let min = left.count > right.count ? right.count : left.count for i in 0..<min { if left[left.index(left.startIndex, offsetBy: i)] != right[right.index(right.startIndex, offsetBy: i)] { return (left as NSString).substring(with: NSMakeRange(0, i)) } } return (left as NSString).substring(with: NSMakeRange(0, min)) }
三、二分查找法
思路：
应用二分查找法找到所有字符串的公共前缀的最大长度 L。 算法的查找区间是 (0…minLen)(0…minLen)，其中 minLen 是输入数据中最短的字符串的长度，同时也是答案的最长可能长度。 每一次将查找区间一分为二，然后丢弃一定不包含最终答案的那一个。算法进行的过程中一共会出现两种可能情况：
S[1...mid] 不是所有串的公共前缀。 这表明对于所有的 j > i S[1..j] 也不是公共前缀，于是我们就可以丢弃后半个查找区间。
S[1...mid] 是所有串的公共前缀。 这表示对于所有的 i < j S[1..i] 都是可行的公共前缀，因为我们要找最长的公共前缀，所以我们可以把前半个查找区间丢弃。
时间复杂度：O(n*log(m))，n为所有字符串中字符数量的总和，m代表m个长度为s的相同字符串
具体实现：
func longestCommonPrefix(_ strs: [String]) -> String { if strs.count == 0 { return "" } //找到输入的数据中最短的字符串的长度 var minCount = strs[0].count for i in 1..<strs.count { minCount = (minCount>strs[i].count) ? strs[i].count : minCount } var low = 1 var hight = minCount while low <= hight { let mid = (low+hight)/2 if isCommonPrefix(strs, mid){ //如果s[0...mid]是所有串的公共前缀，于是可以丢弃前半个查找区间 low = mid + 1 }else{ //如果s[0...mid]不是所有串的公共前缀，于是可以丢弃后半个查找区间 hight = mid - 1 } } return (strs[0] as! NSString).substring(with: NSMakeRange(0, (low+hight)/2)) } func isCommonPrefix(_ strs : [String], _ len : Int)->Bool{ let str = (strs[0] as! NSString).substring(with: NSMakeRange(0, len)) for i in 1..<strs.count { if !strs[i].hasPrefix(str) { return false } } return true }
