Go 和 PHP 实现计算最长公共前缀

获取最长公共前缀

author: he xiaodong date: 2020-04-15

原文链接:go leetcode,php 代码个人原创

最长公共前缀(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
}

PHP 实现

function longestCommonPrefix($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 longestCommonPrefix(['张A', '张ABC', '张C', '张哈哈']); // output:张
// echo longestCommonPrefix(['abs', 'abx', 'abb', 'abd']); // output:ab
// echo longestCommonPrefix(['abs']); // output:abs