[Leedcode][JAVA][第14题][最长公共前缀][二分][横竖扫描][分治]

约定不等于承诺〃 2023-02-18 01:50 4阅读 0赞

#### 【问题描述】\[中等\] ####

编写一个函数来查找字符串数组中的最长公共前缀。
    
    如果不存在公共前缀，返回空字符串 ""。
    
    示例 1:
    
    输入: ["flower","flow","flight"]
    输出: "fl"
    示例 2:
    
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    说明:
    
    所有输入只包含小写字母 a-z 。

#### 【解答思路】 ####

###### 1. 横向扫描 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) { 
                return "";
            }
            String prefix = strs[0];
            int count = strs.length;
            for (int i = 1; i < count; i++) { 
                prefix = longestCommonPrefix(prefix, strs[i]);
                if (prefix.length() == 0) { 
                    break;
                }
            }
            return prefix;
        }
    
        public String longestCommonPrefix(String str1, String str2) { 
            int length = Math.min(str1.length(), str2.length());
            int index = 0;
            while (index < length && str1.charAt(index) == str2.charAt(index)) { 
                index++;
            }
            return str1.substring(0, index);
        }
    }

###### 2. 纵向扫描 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) { 
                return "";
            }
            int length = strs[0].length();
            int count = strs.length;
            for (int i = 0; i < length; i++) { 
                char c = strs[0].charAt(i);
                for (int j = 1; j < count; j++) { 
                    if (i == strs[j].length() || strs[j].charAt(i) != c) { 
                        return strs[0].substring(0, i);
                    }
                }
            }
            return strs[0];
        }
    }

public String longestCommonPrefix(String[] strs) { 
            if (strs.length == 0) return "";
            for(int i= 0;i<strs[0].length();++i){ 
                for(int j=1 ; j<strs.length;j++){ 
                    if(i == strs[j].length() || strs[j].charAt(i)!=strs[0].charAt(i)){ 
                        return strs[0].substring(0,i);
                    }
                }
            }
    
            return strs[0];
    
        }

###### 2. 二分法 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
**时间复杂度：O(mnlogm) 空间复杂度：O(1)**

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) { 
                return "";
            }
            int minLength = Integer.MAX_VALUE;
            for (String str : strs) { 
                minLength = Math.min(minLength, str.length());
            }
            int low = 0, high = minLength;
            while (low < high) { 
                int mid = (high - low + 1) / 2 + low;
                if (isCommonPrefix(strs, mid)) { 
                    low = mid;
                } else { 
                    high = mid - 1;
                }
            }
            return strs[0].substring(0, low);
        }
    
        public boolean isCommonPrefix(String[] strs, int length) { 
            String str0 = strs[0].substring(0, length);
            int count = strs.length;
            for (int i = 1; i < count; i++) { 
                String str = strs[i];
                for (int j = 0; j < length; j++) { 
                    if (str0.charAt(j) != str.charAt(j)) { 
                        return false;
                    }
                }
            }
            return true;
        }
    }

###### 4. 分治 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
**复杂度**  
![在这里插入图片描述][20200615104249789.png]

#### 【总结】 ####

###### 1.纵横交错 二分分治 ######

###### 2. 字符串/数组题目遍历 暴力再优化 ######

#  #

转载链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615103332358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615103437309.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200615104039602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200615104228529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200615104249789.png]: https://img-blog.csdnimg.cn/20200615104249789.png