// 力扣14. 最长公共前缀
// https://leetcode.cn/problems/longest-common-prefix/
package main

import "fmt"

// 先计算数组中最短的字符串长度，在这个长度范围内，从头比较数组中每一个字符串相同位置的字符是否都相同。
// 空间复杂度 O(1)，时间复杂度 O(S)，S 是所有字符串中字符数量的总和。
// 最坏情况下，输入数据为n个长度为m的相同字符串，会进行 S = m*n 次比较；
// 最好的情况下，只需要进行 n * min(Len(N)) 次比较，其中 min(Len(N)) 是数组中最短字符串的长度。
func longestCommonPrefix1(strs []string) string {
	length := len(strs)
	if length == 0 {
		return ""
	}
	minLen := len(strs[0])
	tmp := 0
	for i := 1; i < length; i++ {
		tmp = len(strs[i])
		if tmp < minLen {
			minLen = len(strs[i])
		}
	}
	result := ""
	for j := 0; j < minLen; j++ {
		for k := 0; k < length-1; k++ {
			if strs[k][j] != strs[k+1][j] {
				return result
			}
		}
		result += string(strs[0][j])
	}
	return result
}

// 依次假设最长公共前缀长度为0到len(strs[0]) ，在每一轮循环中只要strs中存在比当前最长公共前缀长度更短的字符串，
// 或者strs中存在和当前 index 字符不相同的字符串，就返回上一轮的最长公共前缀，如果一直没返回，说明strs[0]就是最长公共前缀。
// 时间复杂度: O(N * len(strs(0))，空间复杂度: O(1)。
func longestCommonPrefix2(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	for i := 0; i < len(strs[0]); i += 1 {
		for _, str := range strs {
			// 只要strs中存在比当前长度i更短的string，立刻返回上一轮LCP，即strs[0][:i]
			// 只要strs中存在当前index字符与LCP该index不相同的字符串，立刻返回上一轮LCP，即strs[0][:i]
			if len(str) <= i || strs[0][i] != str[i] {
				return strs[0][:i]
			}
		}
	}
	return strs[0] // 如果一直没返回，说明strs[0]本身就是LCP，返回它
}

func main() {
	fmt.Println(longestCommonPrefix1([]string{"flower", "flow", "flight"})) //fl
	fmt.Println(longestCommonPrefix1([]string{"dog", "racecar", "car"}))    //""

	fmt.Println(longestCommonPrefix2([]string{"flower", "flow", "flight"})) //fl
	fmt.Println(longestCommonPrefix2([]string{"dog", "racecar", "car"}))    //""
}