LeetCode14.最长公共前缀(Kotlin语言)

题目描述

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

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

示例 1:

输入: ["flower","flow","flight"]

输出: "fl"

示例 2:

输入: ["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

说明:

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

解题思路

1.先计算出数组中的最短字符串长度 shortestStrLen

2.最长公共前缀 <= shortestStrLen

3.for len in 0..shortestStrLen 逐一遍历 strs 中的元素,比对是否相等

4.遇到不相等的 len, 就停止遍历,记录此时的 maxCommonLen = len.

5.注意考虑遍历完 shortestStrLen,都相等的情况, 此时 maxCommonLen = shortestStrLen

代码

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) return ""

        // 数组中的最短的字符串长度
        var shortestStrLen = Int.MAX_VALUE
        strs.forEach {
            shortestStrLen = Math.min(it.length, shortestStrLen)
        }
        if (shortestStrLen == 0) return ""

        val n = strs.size
        var maxCommonLen = 0

        var flag = true
        for (len in 0 until shortestStrLen) {
            for (i in 1 until n) {
                if (strs[i][len] != strs[0][len]) {
                    flag = false
                    break
                }
            }

            // 遍历中断
            if (!flag) {
                maxCommonLen = len
                break
            } else {
                // 全部遍历均相同
                maxCommonLen = shortestStrLen
            }
        }

        return strs[0].subSequence(0, maxCommonLen).toString()
        
    }
}

运行测试

fun main() {
    run {
        val strs = arrayOf("flower", "flow", "flight")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=fl")
    }

    run {
        val strs = arrayOf("dog", "racecar", "car")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=")
    }

    run {
        val strs = arrayOf("doger", "dogeracecar", "dogercar")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=doger")
    }

    run {
        val strs = arrayOf("abca", "aba", "aaab")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=a")
    }

    run {
        val strs = arrayOf("c", "acc", "ccc")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=")
    }

    run {
        val strs = arrayOf("aac", "acab", "aa", "abba", "aa")
        val common = longestCommonPrefix(strs)
        println("common=$common, expected=a")
    }
}

// 输出:
common=fl, expected=fl
common=, expected=
common=doger, expected=doger
common=a, expected=a
common=, expected=
common=a, expected=a

参考资料

https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-kotlinyu-yan-by-chen/

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号,主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界,越需要宁静的思考。

相关文章阅读

动态规划算法图文详解(Kotlin语言):二维矩阵中找到只包含&nbsp;1&nbsp;的最大正方形(LeetCode-221)

Java并发多线程高频面试题

滑动窗口算法原理图解(Kotlin语言)长度最小的子数组-LeetCode209

图文详解布隆过滤器(Bloom Filter):如何快速判断某URL是否在20亿的网址URL集合中?

LRUCache的几种Java实现

【BAT面试题宝库附详尽答案解析】图解分布式一致性协议Paxos算法

Linux内核的 4 大 IO 调度算法

如何设计一个消息中间件? 消息中间件的总体架构

[数据结构与算法]1.冒泡排序(Bubble Sort)

[数据结构与算法]2.快速排序Java实现

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章