# 1638. Count Substrings That Differ by One Character
###### tags: `Leetcode` `Medium` `Greedy` `Three Pass` `Dynamic Programming`
Link: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/description/
## 思路
思考如果我们发现s[i], t[j]不一样 我们应该如何count包含s[i], t[j]的valid substring的个数
我们只需要找到```s[i]```和```t[j]```**之前**有多少个连续的、相等的字符的个数```a```

然后对于两个不相同的s[i]和t[j] count就是```(a+1)*(b+1)```
## Code

class Solution:
def countSubstrings(self, s: str, t: str) -> int:
m, n = len(s), len(t)
front = [[0 for j in range(n+2)] for i in range(m+2)]
end = [[0 for j in range(n+2)] for i in range(m+2)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1]==t[j-1]:
front[i][j] = front[i-1][j-1]+1
for i in range(m, 0, -1):
for j in range(n, 0, -1):
if s[i-1]==t[j-1]:
end[i][j] = end[i+1][j+1]+1
ans = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1]==t[j-1]: continue
ans += (front[i-1][j-1]+1)*(end[i+1][j+1]+1)
return ans

class Solution {
public int countSubstrings(String s, String t) {
int m = s.length(), n = t.length();
int[][] front = new int[m+2][n+2];
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s.charAt(i-1)==t.charAt(j-1)) front[i][j] = front[i-1][j-1]+1;
}
}
int[][] end = new int[m+2][n+2];
for(int i=m; i>=1; i--){
for(int j=n; j>=1; j--){
if(s.charAt(i-1)==t.charAt(j-1)) end[i][j] = end[i+1][j+1]+1;
}
}
int ans = 0;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s.charAt(i-1)==t.charAt(j-1)) continue;
ans += (front[i-1][j-1]+1)*(end[i+1][j+1]+1);
}
}
return ans;
}
}