题目
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Constraints:
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.
题解
这道题目的简单描述就是找一堆字符串的相同前缀，比如flower、flow、flight，发现每个字符串都有前缀fl，于是就将fl返回即可，本题就是要实现这样一个在字符串数组中找最长前缀的函数。
解法一：暴力
//Go
func longestCommonPrefix(strs []string) string {
//排除特殊情况
if len(strs) == 0 {
return ""
}
if len(strs) == 1 {
return strs[0]
}
res := strs[0] //获取字符串数组里的第一个元素
for _, v := range strs[1:] { //从字符串数组第二个元素开始遍历
var i int
for ; i < len(v) && i < len(res); i++ { //遍历两数组里的元素
if res[i] != v[i] { //做判断，如果不相等
break //直接结束循环
}
}
res = res[:i]
if res == "" {
return res //返回空
}
}
return res
}
另一种相似解法，会用到strings.Index
//Go
func longestCommonPrefix(strs []string) string {
if len(strs) < 1 {
return ""
}
prefix := strs[0]
for _,k := range strs {
for strings.Index(k,prefix) != 0 {
if len(prefix) == 0 {
return ""
}
prefix = prefix[:len(prefix) - 1]
}
}
return prefix
}
执行结果：
力扣：
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.3 MB, 在所有 Go 提交中击败了55.76%的用户
leetcode：
Runtime: 0 ms, faster than 100.00% of Go online submissions for Longest Common Prefix.
Memory Usage: 2.4 MB, less than 100.00% of Go online submissions for Longest Common Prefix.
