HackerRank算法题：统计oldWord中按序非连续出现newWord的次数

核心逻辑说明 #

你需要统计的是子序列的出现次数：子序列仅要求字符保持原有顺序，不需要连续，是经典的动态规划适用场景。

动态规划解法思路 #

定义dp[i][j]为newWord的前i个字符，在oldWord的前j个字符中的有效出现次数：

• 边界条件：
  • 空字符串是任何字符串的子序列，因此dp[0][任意j] = 1
  • 非空字符串不可能是空串的子序列，因此dp[任意i>0][0] = 0
• 状态转移规则：
  • 如果newWord[i-1] == oldWord[j-1]：当前字符可以用来匹配，总次数 = 不用当前字符的次数 + 用当前字符匹配时前面字符的匹配次数，即dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
  • 如果newWord[i-1] != oldWord[j-1]：当前字符无法匹配，直接继承不用当前字符的次数，即dp[i][j] = dp[i][j-1]

代码实现（PHP示例） #

function countSubsequence(string $newWord, string $oldWord): int {
    $m = strlen($newWord);
    $n = strlen($oldWord);
    // 初始化dp数组
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
    // 边界条件：空串匹配次数为1
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = 1;
    }
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($newWord[$i-1] == $oldWord[$j-1]) {
                $dp[$i][$j] = $dp[$i][$j-1] + $dp[$i-1][$j-1];
            } else {
                $dp[$i][$j] = $dp[$i][$j-1];
            }
        }
    }
    return $dp[$m][$n];
}

// 测试示例1
echo countSubsequence('abc', 'abcababc'); // 输出7
// 测试示例2
echo countSubsequence('ccc', 'cccc'); // 输出4

空间优化版本 #

因为状态转移仅依赖上一行的结果，可以将二维数组压缩为一维，空间复杂度从O(mn)降到O(n)：

function countSubsequenceOptimized(string $newWord, string $oldWord): int {
    $m = strlen($newWord);
    $n = strlen($oldWord);
    $dp = array_fill(0, $m + 1, 0);
    $dp[0] = 1;
    for ($j = 0; $j < $n; $j++) {
        // 倒序遍历避免覆盖需要用到的前一个值
        for ($i = $m; $i >= 1; $i--) {
            if ($oldWord[$j] == $newWord[$i-1]) {
                $dp[$i] += $dp[$i-1];
            }
        }
    }
    return $dp[$m];
}

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