package array_and_string

/*
14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 
提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
*/

func longestCommonPrefix(strs []string) string {
	// 异常参数校验
	if strs == nil || len(strs) == 0 {
		return ""
	}

	// 以第一个字符串为基准，后续的字符串依次与这个字符串进行对比
	aimStr := strs[0]
	// 设置后续遍历索引，之所以设置为1，是为了跳过第一个字符串
	curIndex := 1
	// 依次循环切片中的每一个字符串
	for curIndex < len(strs) {
		// 设置临时索引，维护当前循环对比的两个字符串的公共前缀长度
		tempIndex := 0
		// 内循环以基准字符串的长度为限
		// 最长公共前缀的长度，肯定不会超过基准字符串的长度
		for i, _ := range aimStr {
			// 1. i < len(strs[curIndex]) 是为了防止数组越界
			// 2. aimStr[i] == strs[curIndex][i] 是为了依次对比相同的字符
			if i < len(strs[curIndex]) && aimStr[i] == strs[curIndex][i] {
				// 如果满足上述 if 条件，则说明对比的两个字符前 i 个字符都相同
				// 将临时索引 +1，维护当前对比的两个字符串的最长公共前缀
				tempIndex++
			} else {
				// 如果不满足上述 if 条件，则直接跳出循环
				break
			}
		}

		// 每次循环完之后，按 tempIndex 截取基准字符串
		// 截取后的基准字符串，即为当前最长公共前缀
		aimStr = aimStr[:tempIndex]
		// 将后续遍历索引 +1，继续下一次循环
		curIndex++
	}

	// 循环完之后，基准字符串即为最长公共前缀
	return aimStr
}