LeetCode 最长公共前缀 14. Longest Common Prefix

快来打我* 2022-03-09 05:40 108阅读 0赞

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:
    
    Input: ["flower","flow","flight"]
    Output: "fl"
    Example 2:
    
    Input: ["dog","racecar","car"]
    Output: ""
    Explanation: There is no common prefix among the input strings.
    Note:

All given inputs are in lowercase letters a-z.  
  给我们一个字符串数组，判断这个字符串数组中每个字符串最长的公共前缀，例子见上。  
  给我们第一反应就是循环拿到每个字符串从第一个字符开始对比，当字符之间存在不相等的情况则跳出循环，则之前遍历的字符组成的字符串就是最大前缀。

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) return "";//null或者空字符串返回“”
            
            for(int i = 0 ;i < strs[0].length();i++){ 
                char c = strs[0].charAt(i);//从头拿到第一个字符串每个字符
                
                for(int j = 1;j < strs.length;j++){ //依次和后面的字符串进行比较
                    if (i == strs[j].length() || strs[j].charAt(i) != c)//发生不等或者比较的字符位置等于某个字符串长度则返回已经遍历了的字符
                        return strs[0].substring(0,i);
                }
                
            }
            return strs[0];
        }
    }

JDK里面对数组提供了一些工具类方法，下面提供一个思路清奇的解法，先将字符串数组进行字典排序，然后只用对比第一个字符串和最后一个字符串的最大公共前缀即可，注意：不是单纯找最长串和最段串，是找字典排序情况下的最长串和最短串。

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) return "";
            Arrays.sort(strs);//字典排序
            
            for(int i = 0;i < strs[0].length();i++){ 
                if(strs[0].charAt(i)!=strs[strs.length-1].charAt(i))//比较字典排序情况下最短串和最长串
                    return strs[0].substring(0,i);
            }
            
            return strs[0];
        }
    }

为什么是字典顺序下的？见下：

输入 abad aba abc
    字典序 aba abc abad

如果是上面的输入不进行字典排序，那么取最长串和最短串会发生比较abad和abc，最大公共前缀是ab，错误，而进行了字典排序则不会。