统计只差一个字符的子串数目
难度:
标签:
题目描述
代码结果
运行时间: 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]`具体代表什么含义?请详细解释它们在算法中的作用。
▷🦆
题解中提到,当`s[i]`不等于`t[j]`时,`dp[i][j]`的值设为`pre[i-1][j-1] + 1`。这里的`+1`是如何合理地反映这两个子字符串恰好有一个字符不同的情况?
▷🦆
算法中如何处理两个字符串开始位置的边界条件?即`s`和`t`在字符串的起始位置如何初始化`pre`和`dp`数组?
▷