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

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

function longestCommonPrefix(strs: string[]): string {
    // 按顺序比较每个字符串
    let s: string = ''
    let n = strs.length
    if(n === 0) return ''
    if(n === 1) return strs[0]
    let minLength = strs[0].length // 单词的最短长度
    for(let i=0; i<n; i++){
            minLength = Math.min(minLength, strs[i].length)
    }
    for(let i=0; i<minLength; i++){ // 比较第i个位置的单词
        for(let j=0; j<n; j++){
            if(strs[0][i] === strs[j][i]){
                continue;
            }else{
                // 前缀不一致了，直接返回
                return s
            }
        }
        s += strs[0][i] // 前缀增长
    }
    return s
};

function longestCommonPrefix(strs: string[]): string {
    // 边界条件1：空数组直接返回空字符串
    if (strs.length === 0) {
        return "";
    }

    // 1. 对字符串数组进行字典序排序
    const sortedStrs = [...strs].sort(); // 展开原数组再排序，避免修改原数组
    // 2. 取排序后的最小串（第一个元素）和最大串（最后一个元素）
    const minStr = sortedStrs[0];
    const maxStr = sortedStrs[sortedStrs.length - 1];
    // 3. 逐字符比较，构建公共前缀
    let prefix = "";

    // 遍历最小串和最大串的最小长度范围内的字符
    const minLength = Math.min(minStr.length, maxStr.length);
    for (let i = 0; i < minLength; i++) {
        if (minStr[i] === maxStr[i]) {
            // 字符相同，追加到前缀中
            prefix += minStr[i];
        } else {
            // 字符不同，直接终止循环
            break;
        }
    }

    return prefix;
}