抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

Leetcode 14. 最长公共前缀

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)。使用的额外空间复杂度为常数。

解法二:纵向扫描

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

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


0条评论

发表评论