PHP计算查找多个字符串最长公共前缀

发表于 2022年09月21日
PHP

查找两个字符串的最大相同部分

最长公共前缀（Longest-Common-Prefix）

题干如下：

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

解题思路

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

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

至于如何求公共前缀 P，流程图如下：

查找多个字符串的公共前缀

在多个、数组字符串中查找最长公共子串

<?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(['ABCAF12', 'ABCA2', 'ABCFS', 'ABCSD2']);

<?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(['ABCAF12', 'ABCA2', 'ABCFS', 'ABCSD2']);

方法二

<?php
function commonPrefix($arr)
{
	$count = strlen($arr[0]);
	for ($i = 0; $i < count($arr); $i++) {
		if (strlen($arr[$i]) <= $count) {
			$count = strlen($arr[$i]);
		}
	}
	$prefix = '';
	for ($i = 0; $i < $count; $i++) {
		$char = $arr[0][$i];
		$flag = true;
		foreach ($arr as $val) {
			if ($char != $val[$i]) {
				$flag = false;
				break;
			}
		}
		if (!$flag) break;
		$prefix .= $char;
	}
	return $prefix;
}

echo commonPrefix(['5532', '5532ABC', '5532C', '5532哈哈']);

<?php

function commonPrefix($arr)

{

$count = strlen($arr[0]);

for ($i = 0; $i < count($arr); $i++) {

if (strlen($arr[$i]) <= $count) {

$count = strlen($arr[$i]);

}

$prefix = '';

for ($i = 0; $i < $count; $i++) {

$char = $arr[0][$i];

$flag = true;

foreach ($arr as $val) {

if ($char != $val[$i]) {

$flag = false;

break;

}

if (!$flag) break;

$prefix .= $char;

}

return $prefix;

}

echo commonPrefix(['5532', '5532ABC', '5532C', '5532哈哈']);

查找2个字符串的最长公共前缀子串

<?php
function findStr($str1, $str2)
{
	//将字符串转成数组
	$arr1 = str_split($str1);
	$arr2 = str_split($str2);
	//计算字符串的长度
	$len1 = strlen($str1);
	$len2 = strlen($str2);
	//初始化相同字符串的长度
	$len = 0;
	//初始化相同字符串的起始位置
	$pos = -1;
	for ($i = 0; $i < $len1; $i++) {
		for ($j = 0; $j < $len2; $j++) {
			//找到首个相同的字符
			if ($arr1[$i] == $arr2[$j]) {
				//判断后面的字符是否相同
				for ($p = 0; (($i + $p) < $len1) &&
					(($j + $p) < $len2) &&
					($arr1[$i + $p] == $arr2[$j + $p]) &&
					($arr1[$i + $p] <> ''); $p++);
				if ($p > $len) {
					$pos = $i;
					$len = $p;
				}
			}
		}
	}
	if ($pos == -1) {
		return;
	} else {
		return substr($str1, $pos, $len);
	}
}
echo findStr("abcdsss", "sdcdsrf");