14. 最长公共前缀

这里解法有比较多，官方提供了多种：最长公共前缀

解法一：横向扫描

思路：默认取第一个作为最长前缀，然后依次遍历其余字符串的每个元素与默认的最长前缀进行对比。不断缩小最长前缀的范围，最后剩下的就是结果。

后来看到这篇清晰易懂：画解算法：14. 最长公共前缀，其实也就是官方的解法一（横向扫描）。

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        var ans = strs[0]
        for (i in 1 until strs.size) {
            var j = 0
            while (j < ans.length && j < strs[i].length) {
                if (ans[j] != strs[i][j]) break
                j++
            }
            ans = strs[i].substring(0, j)
            if (ans.isEmpty()) return ""
        }
        return ans
    }
}

实际上官方的解法还做了一下优化：

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        var ans = strs[0]
        for (i in 1 until strs.size) {
            var j = 0
            val len = Math.min(ans.length, strs[i].length)
            while (j < len && j < len && ans[j] == strs[i][j]) j++
            ans = strs[i].substring(0, j)
            if (ans.isEmpty()) return ""
        }
        return ans
    }
}

在两篇题解的时间复杂度上，个人觉得官方的更准确一些，效率上也高一点。

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

解法二：纵向扫描

只是换了下方位，可以写一遍，不难理解。

其他解法：一定程度上要么增加的时间复杂度，要么增加了空间复杂度，目前不在我的考虑范围内，略过。