一、題目
編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴嫡良。
如果不存在公共前綴袜炕，返回空字符串 ""本谜。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。
說明:
所有輸入只包含小寫字母 a-z 偎窘。
二乌助、解題
這題比較簡(jiǎn)單，直接暴力遍歷即可陌知，但也有兩種方式他托，
方法一：
是直接依次匹配第n個(gè)是否相同，相同拼接到公共前綴上仆葡，一旦發(fā)現(xiàn)不匹配的情況直接返回赏参。
假設(shè)第一個(gè)字符串長度為m，數(shù)組的數(shù)量為n沿盅，時(shí)間復(fù)雜度為O(m * n),空間復(fù)雜度為O(1).
方法二：
是先默認(rèn)數(shù)組中第一個(gè)字符串為公共前綴把篓，然后遍歷判斷其他字符串是否有這個(gè)公共前綴，如果沒有腰涧，則清除最后一位繼續(xù)匹配韧掩，直到所有的字符串都有這個(gè)前綴或者前綴為空時(shí)返回。
假設(shè)第一個(gè)字符串長度為m南窗，數(shù)組的數(shù)量為n揍很，時(shí)間復(fù)雜度為O(m * n),空間復(fù)雜度為O(1).
三、代碼實(shí)現(xiàn)
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
if strs.count == 0{
return ""
}else if strs.count == 1 {
return strs.first!
}else{
var result = ""
for (index, a) in strs.first!.enumerated() {
for str in strs[1..<strs.count] {
if index < str.count {
if a != str[str.index(str.startIndex, offsetBy: index)] {
return result
}
}else{
return result
}
}
result.append(a)
}
return result
}
}
func longestCommonPrefix1(_ strs: [String]) -> String {
if strs.count == 0{
return ""
}else if strs.count == 1 {
return strs.first!
}else{
var result = strs[0]
for i in 1..<strs.count {
let str = strs[i]
while !str.hasPrefix(result) {
result = String(result.prefix(result.count - 1))
if result.isEmpty {
return ""
}
}
}
return result
}
}
}
Demo地址：github
