最长公共前缀LCP

最长公共前缀 LCP(longest common prefix)

Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

思路：先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可
eg：["abcddd","abbddd","abccc"] -> ["abbddd","abccc"，"abcddd"],
只需比较第一个字符串"abbddd"与最后一个字符串"abcddd"

代码实现

/** * 最长公共前缀 LCP(longest common prefix) * Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 * * 思路：先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可 * eg：["abcddd","abbddd","abccc"] -> ["abbddd","abccc"，"abcddd"], * 只需比较第一个字符串"abbddd"与最后一个字符串"abcddd" */public class LCP {    public String solution(String[] strs){        //保存公共前缀        StringBuffer lcpStr = new StringBuffer();        if(strs == null){            return lcpStr.toString();        }        //排序        Arrays.sort(strs);        String first = strs[0];        String last = strs[strs.length - 1];        int firstLength = first.length();        int lastLength = last.length();        int count = firstLength > lastLength ? lastLength : firstLength;        for(int i = 0;i < count;i++){            if(first.charAt(i) == last.charAt(i)){                lcpStr.append(first.charAt(i));            }else{                //不一样则退出循环                break;            }        }        return lcpStr.toString();    }    public static void main(String[] args) {        LCP lcp = new LCP();        String[] strs = {"abcddd","abbddd","abccc"};        System.out.println(lcp.solution(strs));    }}