1, 题目

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

如果不存在公共前缀，返回空字符串 “”。
示例 1:

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

示例 2:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

1, 排序

  1. 第一步, 排序
  2. 第二步, 比较最大最小的公共前缀就是整个数组的公共前缀
  1. #scala实现
  2. object Solution {
  3.     def longestCommonPrefix(strs: Array[String]): String = {
  4.         if (strs.isEmpty) {
  5.             return ""
  6.         }
  7.         val arr = strs.sorted
  8.         val s1 = arr(0)
  9.         val s2 = arr.last
  10.         s1.zip(s2).takeWhile(x => x._1 == x._2).map(x => x._1).mkString("")
  11.     }
  12. }
#python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        strs = sorted(strs)
        str_min = strs[0]
        str_max = strs[-1]

        for index, value in enumerate(str_min):
            if value != str_max[index]:
                return str_min[:index]
        return str_min