leetcode 14 Longest Common Prefix

suosuopuo 发布于2019-08-16 11:04 / 734人阅读

摘要：题目详情题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。

题目详情

Write a function to find the longest common prefix string amongst an array of strings. 题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。

想法

一种想法是先将数组的第一个元素赋值为前缀，然后不断找出它和后边的字符串所重叠的部分。（水平扫描）

但是这个方法有一个弊端，如果前面的元素特别长，而后面的元素又很短。就会产生较多的多余计算。

为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。

解法一水平扫描

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)return "";
        String prefix = strs[0];       
        if(strs.length ==1) return prefix;
        
        for(int i=1;i
解法二 垂直扫描

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    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];
}

专线服务服务器托管 Common Longest prefix prefix策略

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

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

# 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
# Leetcode 14：Longest Common Prefix 最长公共前缀

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

FrancisSoung 2019-08-16 18:25 评论0 收藏0
leetcode 14 Longest Common Prefix

摘要：题目详情题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。题目详情 Write a function to find the longest common prefix string amongst an array of strings. 题目要求是，给定一个字符串的数组，我们要...

jackwang 2019-08-14 18:00 评论0 收藏0
【LeetCode Easy】014 Longest Common Prefix

摘要：注意要检查参数数组是否为空或循环找出数组中最短的那个单词，以这个单词为基准，两层循环嵌套，外层是遍历这个最短单词的每一个字母，内层是遍历所有单词，看其它单词这个位置的字母是否和最短单词一样，若都一样，继续向下遍历，若有不一样的，，返回当前的 Easy 014 Longest Common Prefix Description： find the longest common prefi...

BDEEFE 2019-08-16 16:54 评论0 收藏0
[LeetCode] Longest Common Prefix

摘要：我的思路是用对中的字符串逐个遍历第位的字符，如果都相同，就把这个字符存入，否则返回已有的字符串。注意，第二层循环的条件的值不能大于。 Problem Write a function to find the longest common prefix string amongst an array of strings. Note 我的思路是用StringBuilder对strs中的字...

ivan_qhz 2019-08-14 14:03 评论0 收藏0