一、题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
二、思路讲解
逐位更新公共前缀。将所有字符串的第i位（从0开始）与第一个字符串的第i位比较。如果第i位都相同，说明是相同前缀，将它追加到要返回的字符串s（初始为空串）上；如果有不相同，直接返回 s；
三、Java代码实现
class Solution { public String longestCommonPrefix(String[] strs) { String s = ""; int len = strs[0].length(); for(int i=0; i<strs.length; i++){ if(len > strs[i].length()){ len = strs[i].length(); } } for(int i=0; i<len; i++){ char temp = strs[0].charAt(i); for(int j=1; j<strs.length; j++){ if(temp != strs[j].charAt(i)){ return s; } } s += temp; } return s; } }
四、时空复杂度分析
时间复杂度： O(MN) M是数组中字符串平均长度，N是数组长度。最坏情况需要遍历数组中所有字符串
空间复杂度： O(1)
五、代码优化
直接将s初始化为最短的字符串，然后逐一判断数组中所有的字符串是否以s开头。若不，那么将s更新为二者的共同前缀。
class Solution { public String longestCommonPrefix(String[] strs) { String s = strs[0]; //令s为最短的字符串 for(int i=0; i<strs.length; i++){ if(strs[i].length() < s.length()){ s = strs[i]; } } for(int i=0; i<strs.length; i++){ //判断第i个字符串的前缀是不是s，如果不是，取共同前缀 if(!strs[i].startsWith(s)){ s = sub(strs[i], s); } } return s; } //取两个字符串的共同前缀 public static String sub(String a, String b){ int len = Math.min(a.length(), b.length()); int i; for(i=0; i<len; i++){ if(a.charAt(i) != b.charAt(i)){ break; } } return a.substring(0, i); } }
极大减少了运行时间，前面的方法在力扣中需要8ms，打败8%的提交
这个方法只需0ms，打败100%的提交。
