Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in
t by exactly one character.
For example, the underlined substrings in "_compute_ r" and "_computa_ tion" only differ by the 'e'/'a', so this is a valid way.
Return the number of substrings that satisfy the condition above.
A substring is a contiguous sequence of characters within a string.
Input: s ="aba", t ="baba" Output:6 Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:("_a_ ba","_b_ aba")("_a_ ba","ba _b_ a")("ab _a_ ","_b_ aba")("ab _a_ ","ba _b_ a")("a _b_ a","b _a_ ba")("a _b_ a","bab _a_ ") The underlined portions are the substrings that are chosen from s and t.```
#### Example 2
```d Input: s ="ab", t ="bb" Output:3 Explanation: The following are the pairs of substrings from s and t that differ by 1 character:("_a_ b","_b_ b")("_a_ b","b _b_ ")("_ab_ ","_bb_ ")The underlined portions are the substrings that are chosen from s and t.
We want to count all pairs of substrings (one from s, one from t) of the same length that differ by exactly one character. For each possible starting position in s and t, we can compare substrings character by character and count those with exactly one mismatch.
classSolution {
public:int countSubstrings(string s, string t) {
int n = s.size(), m = t.size(), ans =0;
for (int i =0; i < n; ++i) {
for (int j =0; j < m; ++j) {
int diff =0;
for (int k =0; i + k < n && j + k < m; ++k) {
if (s[i + k] != t[j + k]) ++diff;
if (diff >1) break;
if (diff ==1) ++ans;
}
}
}
return ans;
}
};
typeSolutionstruct{}
func (Solution) CountSubstrings(s, tstring) int {
n, m:= len(s), len(t)
ans:=0fori:=0; i < n; i++ {
forj:=0; j < m; j++ {
diff:=0fork:=0; i+k < n&&j+k < m; k++ {
ifs[i+k] !=t[j+k] {
diff++ }
ifdiff > 1 {
break }
ifdiff==1 {
ans++ }
}
}
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicintcountSubstrings(String s, String t) {
int n = s.length(), m = t.length(), ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int diff = 0;
for (int k = 0; i + k < n && j + k < m; ++k) {
if (s.charAt(i + k) != t.charAt(j + k)) ++diff;
if (diff > 1) break;
if (diff == 1) ++ans;
}
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funcountSubstrings(s: String, t: String): Int {
val n = s.length
val m = t.length
var ans = 0for (i in0 until n) {
for (j in0 until m) {
var diff = 0for (k in0 until minOf(n-i, m-j)) {
if (s[i+k] != t[j+k]) diff++if (diff > 1) breakif (diff ==1) ans++ }
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defcountSubstrings(self, s: str, t: str) -> int:
n, m = len(s), len(t)
ans =0for i in range(n):
for j in range(m):
diff =0for k in range(min(n - i, m - j)):
if s[i + k] != t[j + k]:
diff +=1if diff >1:
breakif diff ==1:
ans +=1return ans
impl Solution {
pubfncount_substrings(s: String, t: String) -> i32 {
let n = s.len();
let m = t.len();
let s = s.as_bytes();
let t = t.as_bytes();
letmut ans =0;
for i in0..n {
for j in0..m {
letmut diff =0;
for k in0..std::cmp::min(n-i, m-j) {
if s[i+k] != t[j+k] {
diff +=1;
}
if diff >1 {
break;
}
if diff ==1 {
ans +=1;
}
}
}
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
countSubstrings(s: string, t: string):number {
constn=s.length, m=t.length;
letans=0;
for (leti=0; i<n; ++i) {
for (letj=0; j<m; ++j) {
letdiff=0;
for (letk=0; i+k<n&&j+k<m; ++k) {
if (s[i+k] !==t[j+k]) diff++;
if (diff>1) break;
if (diff===1) ans++;
}
}
}
returnans;
}
}