让我们一起啃算法----最长公共前缀

最长公共前缀(Longest-Common-Prefix)

题干如下:

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
  输入: [“flower”,”flow”,”flight”]
  输出: “fl”
示例 2:
  输入: [“dog”,”racecar”,”car”]
  输出: “”
解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
来源:力扣

解题思路

首先我们从题干入手,求字符串数组的公共前缀,那么什么是公共前缀呢?其实就是所有字符串都有的子串,并且这个子串的位置还比较特殊,它在字符串的开始位置

有了这个认知之后,我们随意取两个字符串 S1S2,先得出 S1S2 的公共前缀,记为 P1。如果没有公共前缀,那么直接返回空字符串,如果存在 P1,那么将 P1S3 比较,得出公共前缀 P2,以此类推。( P1的长度一定是大于等于 P2 )。

至于如何求公共前缀 P,流程图如下:

代码实现

GO语言实现

func longestCommonPrefix(strs []string) string {
    if len(strs) <= 0 {
        return ""
    }
    // 将前缀初始化为第一个元素值
    var prefix = strs[0]
    for i := 1; i< len(strs); i++ {
        // 判断字符串是否是prefix开头的,如果是 strings.Index 返回 0
        if strings.Index(strs[i], prefix) != 0 {
            // 去掉前缀的最后一个字符
            prefix = prefix[:len(prefix)-1]
            // 因为会执行 i++,为了保证 i 不变,先 i--
            i--
        }
    }
    return prefix
}

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀
https://github.com/wx-satellite/learning-a...

本作品采用《CC 协议》,转载必须注明作者和本文链接
三斤
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 6

终于有个我的实力能看懂的算法了

3年前 评论
三斤和他的喵 (楼主) 3年前
function longest_common_prefix (array $arr)
    {
        if (count($arr) < 1) {
            return '';
        }

        sort($arr);
        $keys = array_keys($arr);
        $str1 = $arr[$keys[0]];
        $str2 = $arr[$keys[count($keys) - 1]];
        $prefix = '';
        $len = min(mb_strlen($str1), mb_strlen($str2));
        for ($i = 0; $i < $len; $i++){
            if (mb_substr($str1, $i, 1) !== mb_substr($str2, $i, 1)){
                break;
            }
            $prefix .= mb_substr($str1, $i, 1);
        }

        return $prefix;
    }
    dump(longest_common_prefix(['flower','flow','flight']));
    dump(longest_common_prefix(['你好,张三','你好,李四','你好,王五']));
    dump(longest_common_prefix(['dog','cat','red']));
    dump(longest_common_prefix(['one word']));// 应该返回字符串?还是空? 没得比

数组越多, 效果越明显,key 支持任意,不仅仅是数字

3年前 评论
三斤和他的喵 (楼主) 3年前
kis龍 (作者) 3年前
captain2021 3年前
kis龍 (作者) 3年前
captain2021 3年前
function checkPrefix($strs)
{
   if (count($strs) <= 0) {
        return '';
    }
    // 将前缀初始化为第一个元素值
    $prefix = $strs[0];

    $count = count($strs);
    for ($i = 0; $i < $count; $i++) {
        if ($prefix !== '' && strpos($strs[$i], $prefix) !== 0) {
            $prefix = substr($prefix, 0, -1);
            $i--;
        }
    }

    return $prefix;
}

echo checkPrefix(['张A', '张ABC', '张C', '张哈哈']);

直接在你的基础上改编成了 php 代码,顺带楼主的文章可以发去我博客吗?保留原文和作者的

3年前 评论
三斤和他的喵 (楼主) 3年前

:see_no_evil: 希望不要 🐦

3年前 评论
三斤和他的喵 (楼主) 3年前

养长一点再来看 :+1:

3年前 评论
三斤和他的喵 (楼主) 3年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!