图解LeetCode14：最长公共前缀（递归，二分查找）

柔光的暖阳◎ 2023-10-04 17:14 2阅读 0赞

### LeetCode14：最长公共前缀 ###

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串""。

示例：

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

#### 思路1： ####

**递归法**

我们可以采用各个字符进行比较，比如：将待比较的最大公共前缀为strs\[0\]，就是flowers，然后与strs\[1\]相比，flowers和flow的公共前缀为flow，则更新公共前缀为flow，再与flight相比，公共前缀为f，则返回f。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]

如果再第一次比较，比如dog和racecar相比没有公共前缀，则直接返回""，不用再往下遍历  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 解法1： ####

public String longestCommonPrefix(String[] strs){
        
        // 如果传入参数strs为空，返回""
        if(strs == null || strs.length == 0) return "";
    
        // 将第一个元素作为初始公共字串
        String commonPrefix = strs[0];
        // 遍历strs，比较公共字串
        for (int i = 1; i < strs.length; i++) {
        
            int j = 0;
            // 遍历第i个元素字符串
            while(j < strs[i].length() && j < commonPrefix.length() ){
        
    
                if (strs[i].charAt(j) != commonPrefix.charAt(j)) commonPrefix = strs[i].substring(0,j);
                j ++;
            }
        }
        return commonPrefix;
    }

#### 思路2： ####

**二分法**

可以按照二分法，逐渐的将公共前缀分割，判断是否所有的元素都是以该前缀开头，如果不是，将公共前缀往前继续二分分割，如果是，将公共前缀往后继续二分分割，直到满足最长的公共前缀要求  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]

其实在二分查找最长公共前缀的时候，应该选择最短的那个作为初始公共前缀，因为公共前缀的数值不可能超过最短的那个，所以就是以flow作为初始公共前缀进行二分查找  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 解法2： ####

public String longestCommonPrefix2(String[] strs){
        
        // 如果传入参数strs为空，返回""
        if(strs == null || strs.length == 0) return "";
        // 找到最短的字符串
        String prefix = "";
        int minLen = strs[0].length();
        for (String str : strs) {
        
            if (str.length() <= minLen){
        
                minLen = str.length();
                prefix = str;
            }
            minLen = Math.min(minLen, str.length());
        }
        // 作为二分查找的索引，当左边大于了右边，证明二分查找结束
        int low = 0, high = minLen;
        // 是否strs全部匹配
        boolean isCommon = true;
        // 结果
        String res = "";
        while(low < high){
        
            // 找到二分值
            int mid = (high - low + 1) / 2 + low;
            res = prefix.substring(0, mid);
            isCommon = true;
            // 遍历所有数值
            for (String str : strs) {
        
                // 元素是否全部以前缀开头
                if (!str.startsWith(res)) {
        
                    isCommon = false;
                    high = mid - 1;
                    break;
                }
            }
            if (isCommon) low = mid;
        }
        // 退出循环再次最后一次更新mid
        int mid = (high - low + 1) / 2 + low;
        res = prefix.substring(0, mid);
        return res;
    }

测试

public static void main(String[] args) {
        
    LeetCode14 lc = new LeetCode14();
            System.out.println(lc.longestCommonPrefix(new String[]{
        "flowers", "flow", "flight"}));
            System.out.println(lc.longestCommonPrefix2(new String[]{
        "flowers", "flowww", "flowight"}));
        }

结果

fl
    flow

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/16c8f4a707c84621bf1a750f11e49e47.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/f357f5b97e0049ceb9b2cedd94acb25f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/3826ef92d2ca4a6fac013886ddf04269.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/a126fcaafef74e41afe9163a488b8ff5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16