欢迎来到李耶的频道【LeetCode面试题】。最长公共前缀14.最长公共前缀题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。输入strs [flower,flow,flight] 输出fl 输入strs [dog,racecar,car] 输出 解释输入不存在公共前缀。解法一纵向扫描思路以第一个字符串为基准逐列比较所有字符串的同一位置字符是否相同。一旦发现不同或某个字符串已到末尾立即返回当前已匹配的前缀。functionlongestCommonPrefix(strs){if(!strs||strs.length0)return;if(strs.length1)returnstrs[0];constfirststrs[0];for(leti0;ifirst.length;i){constcharfirst[i];for(letj1;jstrs.length;j){// 如果当前字符串长度不够或字符不匹配if(istrs[j].length||strs[j][i]!char){returnfirst.substring(0,i);}}}returnfirst;}时间复杂度 / 空间复杂度O(S) / O(1)其中 S 是所有字符串中字符数量的总和优势最坏情况下只需比较到最短字符串的长度提前终止面试中最推荐的写法解法二横向扫描思路先取第一个字符串作为公共前缀然后依次与后续每个字符串比较不断缩短公共前缀直到遍历完所有字符串或前缀为空。functionlongestCommonPrefix(strs){if(!strs||strs.length0)return;if(strs.length1)returnstrs[0];letprefixstrs[0];for(leti1;istrs.length;i){while(strs[i].indexOf(prefix)!0){prefixprefix.substring(0,prefix.length-1);if(prefix)return;}}returnprefix;}时间复杂度 / 空间复杂度O(S) / O(1)优势思路直观易于理解劣势前缀可能被多次缩短效率略低于纵向扫描解法三分治法思路将字符串数组分成左右两半分别求出左半部分和右半部分的最长公共前缀然后求两个前缀的公共前缀。functionlongestCommonPrefix(strs){if(!strs||strs.length0)return;if(strs.length1)returnstrs[0];functioncommonPrefix(left,right){constminLenMath.min(left.length,right.length);for(leti0;iminLen;i){if(left[i]!right[i]){returnleft.substring(0,i);}}returnleft.substring(0,minLen);}functiondivideAndConquer(left,right){if(leftright)returnstrs[left];constmidMath.floor((leftright)/2);constleftPrefixdivideAndConquer(left,mid);constrightPrefixdivideAndConquer(mid1,right);returncommonPrefix(leftPrefix,rightPrefix);}returndivideAndConquer(0,strs.length-1);}时间复杂度 / 空间复杂度O(S) / O(m log n)m 为最长公共前缀长度优势体现分治思想适用于大规模数据并行处理劣势实现较复杂面试中不推荐解法对比解法时间 / 空间复杂度优势推荐指数纵向扫描O(S) / O(1)提前终止空间最优⭐⭐⭐⭐⭐横向扫描O(S) / O(1)思路直观易于理解⭐⭐⭐⭐分治法O(S) / O(m log n)体现分治思想可并行⭐⭐⭐扩展题最长公共子序列给定两个字符串返回它们的最长公共子序列的长度。最长公共子串给定两个字符串返回它们的最长公共子串。最长公共前缀允许删除字符给定一个字符串数组你可以删除任意字符求所有字符串的最长公共前缀。“同舟共济患实共之。” —— 《三国志·吴书·孙破虏讨逆传》关注李耶每天一道面试题一起卷起来