最長公共前綴（LCP）

JasonZhang 發(fā)布于2019-08-19 11:43 / 2220人閱讀

摘要：最長公共前綴編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串。思路先將字符串?dāng)?shù)組排序，在比較第一個字符串與最后一個字符串的公共前綴即可，只需比較第一個字符串與最后一個字符串保存公共前綴排序不一樣則退出循環(huán)

最長公共前綴 LCP(longest common prefix)

Leetcode: 編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

思路：先將字符串?dāng)?shù)組排序，在比較第一個字符串與最后一個字符串的公共前綴即可
eg：["abcffffd","abbffffd","abccc"] -> ["abbffffd","abccc"，"abcffffd"],
只需比較第一個字符串"abbffffd"與最后一個字符串"abcffffd"

代碼實現(xiàn)

/**
 * 最長公共前綴 LCP(longest common prefix)
 * Leetcode: 編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。
 *
 * 思路：先將字符串?dāng)?shù)組排序，在比較第一個字符串與最后一個字符串的公共前綴即可
 * eg：["abcffffd","abbffffd","abccc"] -> ["abbffffd","abccc"，"abcffffd"],
 * 只需比較第一個字符串"abbffffd"與最后一個字符串"abcffffd"
 */
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{
                //不一樣則退出循環(huán)
                break;
            }
        }

        return lcpStr.toString();
    }

    public static void main(String[] args) {
        LCP lcp = new LCP();
        String[] strs = {"abcffffd","abbffffd","abccc"};
        System.out.println(lcp.solution(strs));
    }
}