LeetCode-14.最长公共前缀

发表于 分类于

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"
1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

题解

解法1：横向比较

注意：在swift中str.prex(i) 表示 [0 ..< i) 的子串，左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func longestCommonPrefix(_ strs: [String]) -> String {
  func prefixOfInsertion(_ str1: String, _ str2: String) -> String {
    let length = min(str1.count, str2.count)
    var index = 0
    while index < length && str1.prefix(index + 1) == str2.prefix(index + 1) {
      index += 1
    }
    return String(str1.prefix(index))
  }
  
  var res = strs[0]
  for index in 1 ..< strs.count {
    res = prefixOfInsertion(res, strs[index])
  }
  
  return res
}

解法2：纵向比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func longestCommonPrefix2(_ strs: [String]) -> String {
  let count = strs[0].count
  for i in 0 ..< count {
      let prefix = strs[0].prefix(i + 1)
      for str in strs {
          if str.prefix(i + 1) != prefix {
              return String(str.prefix(i))
          }
      }
  }
  
  return strs[0]
}