longest-common-prefix.md

最长公共前缀

题目链接: https://leetcode.cn/problems/longest-common-prefix/

题目描述

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

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

示例 1：

输入：strs = ["flower","flow","flight"]

输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]

输出：""

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

解题思路：

1. 以第一个元素为默认前缀，遍历所有元素，对每个元素的字符从前往后进行遍历，并与前缀进行对比
2. 若字符与前缀中相同位置的字符不想等，则缩减前缀，并退出循环，对下一个元素进行遍历

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		str := strs[i]
		for j := 0; j < len(str) && j < len(prefix); j++ {
			if str[j] != prefix[j] {
				prefix = prefix[:j]
				break
			}
		}
		if len(str) < len(prefix) {
			prefix = str
		}
	}
	return prefix
}

复杂度分析

• 时间复杂度: $$O(n)$$
• 空间复杂度: $$O(1)$$