14.最长公共前缀【简单】

古城微笑少年丶 2022-10-06 00:59 112阅读 0赞

# 14. 最长公共前缀 【简单】 #

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

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

**示例 1：**

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

**示例 2：**

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

**提示：**

>  *  `0 <= strs.length <= 200`
>  *  `0 <= strs[i].length <= 200`
>  *  `strs[i]` 仅由小写英文字母组成

## JAVA代码： ##

### 纵向方法： ###

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
    
             String result = "";
             int n = strs[0].length();
      
             int i = 1;
             while(i<=n){ 
    
                 //保存待判断的公共前缀
                 //以第一个字符串为参考
                 //substring(begin,end)代表截取字符串从begin位置到end位置，但不包含end。
                String pre = strs[0].substring(0,i);
                
                //循环判断所有字符串是否包含该前缀
                for(int j = 1;j<strs.length;j++){ 
                    //不是以pre为前缀就返回。
                    //也可以使用startsWith来判断是否以指定的前缀开始
                    if(strs[j].indexOf(pre)!=0){ 
                        return result;
                    }
                }
                //都包含此前缀，更新结果，继续下一个。
                result = pre;
                i++;
    
             }
             
             return result;
        }
    }

![在这里插入图片描述][20210611183007777.png]

### 横向方法： ###

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
    
              //判断数组是否为空
              if(strs==null||strs.length==0){ 
                  return "";
              }
    
              String pre = strs[0];
              int len =  strs.length;
              //循环获取两个字符的公共前缀，保存留以与下一个字符串比较
              for(int i = 1;i<len;i++){ 
                  pre = getPublicStr(pre,strs[i]);
                  //没有公共前缀，返回。
                  if(pre.length()==0){ 
                      return "";
                  }
              }    
              return pre;   
        }
    
        //判断两个字符串的最大公共前缀
        public String getPublicStr(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);
        }
    }

![在这里插入图片描述][20210611185457878.png]  
官方的第三，四种方法有些简单事务复杂化，所以这里就不展示了。感兴趣的，可以看一看。

> 最长公共前缀【官方解读版】网址：  
> https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/

### 手写总结： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70]

[20210611183007777.png]: /images/20221005/54614a9499bf47a0849457aef97d5d46.png
[20210611185457878.png]: /images/20221005/56d82b12f4aa42f78700e0134e301553.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvYWlsaXFpMTIxMzQ_size_16_color_FFFFFF_t_70]: /images/20221005/49ac7469079d4c6dae07448e19c4df09.png