longest-common-prefix#14

发表于 更新于 分类于 本文字数： 198 阅读时长 ≈ 1 分钟

问题

最长公共前缀#14

Array#findLongestCommonPrefix

定义扩展方法Array<String>#findLongestCommonPrefix:

1
2
3
fun findLongestCommonPrefix(): String{
    // 具体实现
}

单元测试

1
2
3
4
@Test
fun longestCommonPrefix() {
    assert(arrayOf("flower", "flow", "flight").findLongestCommonPrefix() == "fl")
}

解法

  • 当字符串数组为空时，直接返回 “”
  • 令公共字符串前缀 prefix 为 first()
  • 遍历从 1 到 count() 的字符串 cur，然后找出 cur 与 prefix 公共前缀，最终结果即为最长公共前缀
  • 如果查找过程中 prefix 为空，则不存在公共前缀，直接返回 “”
  • 时间复杂度：O(s)，s 为所有字符串长度之和

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 找出最长公共前缀
 */
fun Array<String>.findLongestCommonPrefix(): String {

    if (isEmpty())
        return ""

    var prefix: String = first()

    for (index in 1 until count()) {

        val cur = get(index)

        while (cur.indexOf(prefix) == -1) {

            prefix = prefix.substring(0, prefix.count() - 1)

            if (prefix.isEmpty())
                return ""
        }
    }

    return prefix
}

参考