LeetCode No.14 [Longest Common Prefix]

Description

Write a function to find the longest common prefix string amongst an array of strings.

Leet Code Link


遍历数组并比较前缀

遍历字符串数组,逐个比较并保存相同的前缀,最后输出前缀的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < len(strs); i++ {
str := strs[i]
if str == "" {
return ""
}
for !strings.HasPrefix(str, prefix) {
prefix = prefix[0 : len(prefix)-1]
}
}
return prefix
}

通过排序,比较第一条和最后一条数据的前缀

先对数组进行排序, 然后通过比较第一条和最后一条数据的前缀取得结果。

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
26
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
sort.Strings(strs)
if strs[0] == "" {
return ""
}
if len(strs) == 1 {
return strs[0]
}
first := strs[0]
last := strs[len(strs)-1]
i := 0
for ; i < len(first); i++ {
if i >= len(last) || first[i] != last[i] {
return first[:i]
}
}
return first[:i]
}