leetcode
leetcode 1451 ~ 1500
统计只差一个字符的子串数目

统计只差一个字符的子串数目

难度:

标签:

题目描述

代码结果

运行时间: 38 ms, 内存: 16.3 MB


// Java Stream solution

/*
 * This approach is not naturally suited to streams due to the need for nested loops
 * and mutable state. However, we can simulate the outer loop using IntStream and
 * then use a method to handle the inner logic.
 */

import java.util.stream.IntStream;

public class Solution {
    public int countSubstrings(String s, String t) {
        return IntStream.range(0, s.length())
                .map(i -> (int) IntStream.range(0, t.length())
                        .flatMap(j -> IntStream.range(0, Math.min(s.length() - i, t.length() - j))
                                .mapToObj(k -> new int[] {i, j, k}))
                        .filter(arr -> s.charAt(arr[0] + arr[2]) != t.charAt(arr[1] + arr[2])
                                && IntStream.range(0, arr[2])
                                .allMatch(k -> s.charAt(arr[0] + k) == t.charAt(arr[1] + k)))
                        .count())
                .sum();
    }
}

解释

方法:

本题解采用动态规划的方法来计算只差一个字符的子串数目。首先,定义两个二维数组 pre 和 dp,其中 pre[i][j] 用于存储字符串 s 和 t 在位置 i 和 j 处前面连续匹配的字符数量。dp[i][j] 用于记录以 s[i] 和 t[j] 结尾且恰好有一个字符不同的子字符串的数量。如果 s[i] 等于 t[j],那么 dp[i][j] 直接继承 dp[i-1][j-1] 的值;如果不等,则 dp[i][j] 等于 pre[i-1][j-1] + 1(表示之前的匹配字符数量加上当前不匹配的一个字符)。最后,通过遍历 dp 数组并累加其中的值来计算结果。

时间复杂度:

O(n*m)

空间复杂度:

O(n*m)

代码细节讲解

🦆
在定义动态规划数组`pre`和`dp`时,`pre[i][j]`和`dp[i][j]`具体代表什么含义?请详细解释它们在算法中的作用。
`pre[i][j]`表示字符串`s`和字符串`t`在位置`i`和`j`处之前连续匹配的最长字符数量。这个数组帮助跟踪两个字符串的连续匹配长度,这是计算只差一个字符的子字符串数目的基础。`dp[i][j]`表示以`s[i]`和`t[j]`作为结尾的子字符串中恰好有一个字符不同的子字符串数量。这个数组是核心的动态规划状态,用于记录符合条件的子字符串数量,并通过对其进行累加来得到最终的答案。
🦆
题解中提到,当`s[i]`不等于`t[j]`时,`dp[i][j]`的值设为`pre[i-1][j-1] + 1`。这里的`+1`是如何合理地反映这两个子字符串恰好有一个字符不同的情况?
当`s[i]`与`t[j]`不相等时,这意味着我们发现了一个不匹配的字符。这时,`pre[i-1][j-1]`已经记录了`s`和`t`在`i-1`和`j-1`之前的连续匹配字符数量。通过将这个匹配长度加上当前这一个不匹配的字符(即`+1`),`dp[i][j]`能够反映出以`s[i]`和`t[j]`结尾的子字符串中正好有一个字符不同的情况。这样确保了我们统计的是恰好一个字符不同的子字符串数量。
🦆
算法中如何处理两个字符串开始位置的边界条件?即`s`和`t`在字符串的起始位置如何初始化`pre`和`dp`数组?
为了简化边界条件的处理,题解中在字符串`s`和`t`的开始加上了一个空格,使得索引从1开始。这样,`pre`和`dp`数组的初始化可以在索引0处全部设为0。对于`pre[i][0]`和`pre[0][j]`,因为没有字符可以匹配,所以这些值都是0。同样,`dp[i][0]`和`dp[0][j]`也都初始化为0,因为没有足够的长度来形成子字符串。这种初始化确保了在动态规划过程中,所有的边界条件都被自然而然地处理了。

相关问题