- 发表于
- 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，流程图如下：
查找多个字符串的公共前缀
在多个、数组字符串中查找最长公共子串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
<?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']); |
方法二
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
<?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个字符串的最长公共前缀子串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
<?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"); |
如有侵权请联系:admin#unsafe.sh