LeetCode每日一题 最长公共前缀

最长公共前缀

Description

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

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

示例 1:

输入: ["flower","flow","flight"] 输出: "fl" 示例 2:

输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。

thought

首先考虑几个特殊情况，数组长度为0肯定是返回空字符串了。数组长度为1的时候因为没有参照对象，所以我们把整个字符串返回。接下来就是有两个及更多的情况了：

我们可以考虑把前两个字符串拿出来做比较，拿出两个之中长度最小的string，看看另一个参照的string是否有相同字符，用substring做字符截取，不同则继续往前。

在上面给出的实例1中：

1. 拿出"flower","flow"
2. 取长度最小字符串，即"flow"
3. 发现另一个对比对象"flower"相同的substring是否相同。发现"flower"也含有"flow"
4. 如果没有则继续向前，直到最后一位。没有返回空字符串

code

class Solution {
     public String longestCommonPrefix(String[] strs) {
         String pre = "";
         if(strs.length == 0) {
             return "";
         }
         if(strs.length == 1) {
             return strs[0];
         }
         pre = help(strs[0],strs[1]);
         if(pre == null) {
             return "";
         }
         for(int i = 2;i < strs.length; i++){
             pre = help(pre,strs[i]);
             if(pre == null){
                 return "";
             }
         }
         return pre;
     }
 ​
 ​
     private String help(String s1,String s2) {
         int len = Math.min(s1.length(),s2.length());
         for(int i = len;i>0;i--){
             String t = s1.substring(0,i);
             if(t.equals(s2.substring(0,i))){
                 return t;
             }
         }
         return null;
     }
 }
           

done

感谢。 2020-08-21