最长公共前缀（LCP）

JasonZhang 发布于2019-08-19 11:43 / 2035人阅读

摘要：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。思路先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可，只需比较第一个字符串与最后一个字符串保存公共前缀排序不一样则退出循环

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

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

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

代码实现

/**
 * 最长公共前缀 LCP(longest common prefix)
 * Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
 *
 * 思路：先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可
 * 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{
                //不一样则退出循环
                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));
    }
}

私有云服务器托管最长公共子序列最长公共子串 LCP 最长递增

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77743.html

LeetCode14.最长公共前缀 JavaScript

摘要：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。说明所有输入只包含小写字母。 LeetCode14.最长公共前缀 JavaScript 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例 1: 输入: [flower,flow,flight] 输出: fl...

wind5o 2019-08-23 14:51 评论0 收藏0
字符串数组最长公共前缀

摘要：字符串数组最长公共前缀给出字符串数组，查找这个数组中所有字符串的最长公共前缀思路从开始自增，判断每个字符串位置的字符是否一致，不一致则之前的串为最长公共字符串。利用函数的特点返回可迭代的对象，只要判断长度大于，则表明此元素非公共字符。字符串数组最长公共前缀 Longest Common Prefix 给出字符串数组，查找这个数组中所有字符串的最长公共前缀 Write a funct...

mrli2016 2019-07-25 12:04 评论0 收藏0
＜LeetCode天梯＞Day023 最长公共前缀（切片法） | 初级算法 | Python

摘要：如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住...

kyanag 2021-11-12 10:36 评论0 收藏0
14. 最长公共前缀-----leetcode刷题（python解题）

摘要：题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。 [TOC] 题目 **编写一个函数来查找字符串数组中的最长公共前缀。** 如果不存在公共前缀，返回空字符串。示例 1: 输入: [flower,flow,flight] 输出: fl 示例 2: 输入: [dog,racecar,car] 输出:...

Berwin 2019-07-31 10:38 评论0 收藏0
# Leetcode 14：Longest Common Prefix 最长公共前缀

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。公众号：爱写bug Write a function to find the longest common prefix string amongst an array of strings. If there...

Keagan 2019-07-31 10:38 评论0 收藏0