PHP函数开发：实现正确与猜测转录本数组精准比对

需要实现一个PHP函数compare($correct, $guess)，接收两个数组参数：

• $correct：正确的中文字符转录本数组
• $guess：猜测的中文字符转录本数组

函数需要将两个数组的元素尽可能精准匹配后返回$result数组，通过$result与$correct逐位对比，可直接看出每个字符位置的匹配、错误、缺漏情况。

核心规则 #

• 当$guess元素数量多于$correct时，多余的元素直接舍弃
• 当$guess元素数量少于$correct时，$correct中没有对应$guess元素的位置用空格填充
• 必须处理$guess中出现的连续错误字符、字符缺漏、新增无关字符的场景，保证匹配的精准性

示例 #

输入 #

function compare($correct, $guess);
// 返回 $result

$correct = ['你', '昨', '天', '为', '什', '么', '没', '跟', '我', '们', '打', '游', '戏', '我', '昨', '天', '一', '点', '时', '间', '都', '没', '有', '我', '一', '直', '在', '写', '作', '业', '那', '你', '现', '在', '写', '好', '了', '吗', '周', '末', '有', '时', '间', '吧', '写', '好', '了', '但', '是', '我', '周', '末', '要', '复', '习'];

$guess   = ['你', '昨', '天', '为', '什', '么', '没', '给', '我', '们', '打', '游', '戏', '规', '则', '天', '一', '点', '时', '间', '都', '没', '有', '我', '一', '直', '在', '写', '作', '业', '你', '数', '学', '好', '了', '吗', '周', '末', '有', '时', '间', '吧', '写', '好', '了', '但', '是', '我', '周', '末', '要', '复', '习'];

预期输出 #

$result  = ['你', '昨', '天', '为', '什', '么', '没', '给', '我', '们', '打', '游', '戏', '规', '则', '天', '一', '点', '时', '间', '都', '没', '有', '我', '一', '直', '在', '写', '作', '业', ' ', '你', '数', '学', ' ', '好', '了', '吗', '周', '末', '有', '时', '间', '吧', '写', '好', '了', '但', '是', '我', '周', '末', '要', '复', '习'];

示例说明 #

• 索引7、13、14的元素为不匹配项
• 索引30、34的位置在$correct中有对应字符，但$guess中缺失，故用空格填充

实现思路与代码 #

要精准处理字符的匹配、错误、缺漏，我们可以基于**最长公共子序列（LCS）**的动态规划算法，先找到两个数组中最长的匹配序列，再根据这个序列的位置映射来构建$result数组，确保每个正确字符尽可能对应到猜测中的正确位置，错误和缺漏的位置也能准确标记。

完整PHP代码实现 #

function compare($correct, $guess) {
    $lenCorrect = count($correct);
    $lenGuess = count($guess);
    
    // 构建LCS动态规划表，存储匹配长度和路径方向
    $dp = array_fill(0, $lenCorrect + 1, array_fill(0, $lenGuess + 1, 0));
    $direction = array_fill(0, $lenCorrect + 1, array_fill(0, $lenGuess + 1, ''));
    
    // 填充DP表
    for ($i = 1; $i <= $lenCorrect; $i++) {
        for ($j = 1; $j <= $lenGuess; $j++) {
            if ($correct[$i - 1] === $guess[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                $direction[$i][$j] = 'diag'; // 匹配，来自对角线
            } else {
                if ($dp[$i - 1][$j] >= $dp[$i][$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j];
                    $direction[$i][$j] = 'up'; // 来自上方，correct有字符但guess没有
                } else {
                    $dp[$i][$j] = $dp[$i][$j - 1];
                    $direction[$i][$j] = 'left'; // 来自左方，guess有多余字符
                }
            }
        }
    }
    
    // 回溯DP表，构建correct到guess的位置映射
    $mapCorrectToGuess = array_fill(0, $lenCorrect, -1);
    $i = $lenCorrect;
    $j = $lenGuess;
    
    while ($i > 0 && $j > 0) {
        if ($direction[$i][$j] === 'diag') {
            $mapCorrectToGuess[$i - 1] = $j - 1;
            $i--;
            $j--;
        } elseif ($direction[$i][$j] === 'up') {
            $i--;
        } else {
            $j--;
        }
    }
    
    // 构建$result数组
    $result = [];
    $usedGuessIndices = [];
    
    // 先处理匹配的位置
    foreach ($mapCorrectToGuess as $correctIdx => $guessIdx) {
        if ($guessIdx !== -1) {
            $result[$correctIdx] = $guess[$guessIdx];
            $usedGuessIndices[$guessIdx] = true;
        } else {
            $result[$correctIdx] = ' '; // correct有字符，guess缺失
        }
    }
    
    // 处理guess中未被使用的字符（多余或错误），填充到对应的correct位置
    $currentGuessIdx = 0;
    foreach ($result as $correctIdx => &$val) {
        if ($val === ' ') {
            // 找到第一个未被使用的guess字符
            while ($currentGuessIdx < $lenGuess && isset($usedGuessIndices[$currentGuessIdx])) {
                $currentGuessIdx++;
            }
            if ($currentGuessIdx < $lenGuess) {
                $val = $guess[$currentGuessIdx];
                $usedGuessIndices[$currentGuessIdx] = true;
                $currentGuessIdx++;
            }
            // 如果没有剩余guess字符，保持空格
        }
    }
    
    // 确保$result长度和correct一致
    while (count($result) < $lenCorrect) {
        $result[] = ' ';
    }
    
    return array_values($result);
}

代码说明 #

1. 动态规划表构建：通过DP表计算两个数组的最长公共子序列，同时记录路径方向，用于后续回溯匹配位置。
2. 位置映射生成：回溯DP表，得到$correct中每个字符对应的$guess位置，没有匹配的标记为-1。
3. 结果数组构建：
   • 先根据映射填充匹配的字符，缺失位置填空格
   • 再将$guess中未被匹配的错误/多余字符填充到$correct的空缺位置
   • 确保最终$result长度和$correct完全一致

内容的提问来源于stack exchange，提问作者BlkStormy