leetcode:14最长公共前缀

刺骨的言语ヽ痛彻心扉 2022-01-26 01:35 256阅读 0赞

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

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

**示例 1:**

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

**示例 2:**

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

之前思路是，觉得拿一个字符串，去匹配一个个剩下字符串很麻烦，中间需要考虑的情况很多，写起来实现也没通过，后来看了leetcode上的题解，觉得很精辟，于是记录一下。

1.水平扫描法

首先，我们将描述一种查找一组字符串的最长公共前缀 LCP(S\_1 \\ldots S\_n)LCP(S1…Sn) 的简单方法。 我们将会用到这样的结论：

LCP(S\_1 \\ldots S\_n) = LCP(LCP(LCP(S\_1, S\_2),S\_3),\\ldots S\_n)LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)。

即如果存在最长字符前缀，必然在每一个字符串中都成立，所以，直接拿第一个字符串和第2个字符串去匹配，剩下公共子串，再拿公共子串去匹配剩下的。

最主要的是匹配算法调用的是Java lang包下的api，实现起来的复杂性被减少了。

public String longestCommonPrefix(String[] strs){
    
            if(strs==null)return "";
    
            String str = strs[0];
            
            for(int i = 1 ;i<strs.length;i++){
        
                    while(strs[i].indexof(str)>0){
    
                    str = str.substring(0,str.length()-1);
    
                    if(str.isEmpty)return "";                
    
                    }
            }
    
            return str;
    
        }

api包括indexof,即能返回strs\[i\]是否包含str，返回整数值。

其次是

substring方法，截取字符串，每次减少一位，通过while循环不断减少得到最小子串。

第二种方法是分治法，即通过递归的方法来处理看看就好了

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";    
            return longestCommonPrefix(strs, 0 , strs.length - 1);
    }
    
    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
       }
    }
    
    String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());       
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) )
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }

这种方法，类似处理LCP数组。等有时间再分享这个方法，大家可以自己查询一下。