LeetCode-最长公共前缀(java实现)

﹏ヽ暗。殇╰゛Y 2022-05-18 08:21 32阅读 0赞

题目如图,

![70][]

最开始我的想法是利用双重for循环，对于相邻字符串的每个字符进行比较。例如"flower"和"flow"，最长公共前缀就是'flo'，利用一个计数器保存公共前缀的长度3；然后比较"flow"和"flight"的最长公共前缀，长度为2，也用计数器保存。最后在这个计数器数组中找到最小值，就是整个String数组中所有元素的最长公共前缀的长度。代码如下

public String longestCommonPrefix(String[] strs) {
            if(strs.length == 0)
                return "";
            if(strs == null ) {
                return null;
            }
            if(strs.length == 1) {
                return strs[0];
            }
    
            int minLength = Integer.MAX_VALUE;
            for (int i = 0; i < strs.length; i++) {
                if(minLength > strs[i].length()) {
                    minLength = strs[i].length();
                }
            }
            if(minLength == 0)
                return "";
    
            int[] commons = new int[strs.length-1];
            for (int i = 0; i < strs.length-1; i++) {
                for (int j = 0; j < minLength; j++) {
                    if(strs[i].charAt(j) == strs[i+1].charAt(j)) {
                        commons[i]++;
                    }else
                        break;
                }
            }
    
            int longestCommonPrefix = Integer.MAX_VALUE;
            for(int i=0; i<commons.length; i++) {
                if(longestCommonPrefix > commons[i]) {
                    longestCommonPrefix = commons[i];
                }
            }
    
            return strs[0].substring(0, longestCommonPrefix);
        }

程序用时9ms，然后看到前面有个用时6ms的代码，研究一番觉得甚是巧妙 ，现在贴出来供诸君欣赏

public static String longestCommonPrefix(String[] strs) {
            int count = strs.length;
            String prefix = "";
            if(count != 0){
                prefix = strs[0];
            }
            for(int i=0; i<count; i++){
                //关键代码，不断的从后往前截取字符串，然后与之相比，直到startsWith()返回true
                while(!strs[i].startsWith(prefix)){
                    prefix = prefix.substring(0, prefix.length()-1);
                }
            }
            return prefix;
        }

代码巧妙的利用了java提供的函数，几乎是不费一兵一卒就拿下了这道题目。非常佩服\[鼓掌！鼓掌\]

[70]: /images/20220518/51b335da7a254f53bb6c10730d9a08dc.png