longest-common-prefix#14

问题

最长公共前缀#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")
}

解法

  • 当字符串数组为空时,直接返回 “”
  • 令公共字符串前缀 prefixfirst()
  • 遍历从 1 到 count() 的字符串 cur,然后找出 curprefix 公共前缀,最终结果即为最长公共前缀
  • 如果查找过程中 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
}

参考