Hash Table
String
Dynamic Programming
Enumeration
Description
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.
Example 1:
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", "bab a")
("aba ", "b aba")
("aba ", "bab a")
("ab a", "ba ba")
("ab a", "baba ")
The underlined portions are the substrings that are chosen from s and t.
Example 2:
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", "bb ")
("ab ", "bb ")
The underlined portions are the substrings that are chosen from s and t.
Constraints:
1 <= s.length, t.length <= 100
s
and t
consist of lowercase English letters only.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def countSubstrings ( self , s : str , t : str ) -> int :
ans = 0
m , n = len ( s ), len ( t )
for i , a in enumerate ( s ):
for j , b in enumerate ( t ):
if a != b :
l = r = 0
while i > l and j > l and s [ i - l - 1 ] == t [ j - l - 1 ]:
l += 1
while (
i + r + 1 < m and j + r + 1 < n and s [ i + r + 1 ] == t [ j + r + 1 ]
):
r += 1
ans += ( l + 1 ) * ( r + 1 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public int countSubstrings ( String s , String t ) {
int ans = 0 ;
int m = s . length (), n = t . length ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( s . charAt ( i ) != t . charAt ( j )) {
int l = 0 , r = 0 ;
while ( i - l > 0 && j - l > 0 && s . charAt ( i - l - 1 ) == t . charAt ( j - l - 1 )) {
++ l ;
}
while ( i + r + 1 < m && j + r + 1 < n
&& s . charAt ( i + r + 1 ) == t . charAt ( j + r + 1 )) {
++ r ;
}
ans += ( l + 1 ) * ( r + 1 );
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
int countSubstrings ( string s , string t ) {
int ans = 0 ;
int m = s . size (), n = t . size ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( s [ i ] != t [ j ]) {
int l = 0 , r = 0 ;
while ( i - l > 0 && j - l > 0 && s [ i - l - 1 ] == t [ j - l - 1 ]) {
++ l ;
}
while ( i + r + 1 < m && j + r + 1 < n && s [ i + r + 1 ] == t [ j + r + 1 ]) {
++ r ;
}
ans += ( l + 1 ) * ( r + 1 );
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func countSubstrings ( s string , t string ) ( ans int ) {
m , n := len ( s ), len ( t )
for i , a := range s {
for j , b := range t {
if a != b {
l , r := 0 , 0
for i > l && j > l && s [ i - l - 1 ] == t [ j - l - 1 ] {
l ++
}
for i + r + 1 < m && j + r + 1 < n && s [ i + r + 1 ] == t [ j + r + 1 ] {
r ++
}
ans += ( l + 1 ) * ( r + 1 )
}
}
}
return
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def countSubstrings ( self , s : str , t : str ) -> int :
ans = 0
m , n = len ( s ), len ( t )
f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
g = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
for i , a in enumerate ( s , 1 ):
for j , b in enumerate ( t , 1 ):
if a == b :
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1
for i in range ( m - 1 , - 1 , - 1 ):
for j in range ( n - 1 , - 1 , - 1 ):
if s [ i ] == t [ j ]:
g [ i ][ j ] = g [ i + 1 ][ j + 1 ] + 1
else :
ans += ( f [ i ][ j ] + 1 ) * ( g [ i + 1 ][ j + 1 ] + 1 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public int countSubstrings ( String s , String t ) {
int ans = 0 ;
int m = s . length (), n = t . length ();
int [][] f = new int [ m + 1 ][ n + 1 ] ;
int [][] g = new int [ m + 1 ][ n + 1 ] ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( s . charAt ( i ) == t . charAt ( j )) {
f [ i + 1 ][ j + 1 ] = f [ i ][ j ] + 1 ;
}
}
}
for ( int i = m - 1 ; i >= 0 ; -- i ) {
for ( int j = n - 1 ; j >= 0 ; -- j ) {
if ( s . charAt ( i ) == t . charAt ( j )) {
g [ i ][ j ] = g [ i + 1 ][ j + 1 ] + 1 ;
} else {
ans += ( f [ i ][ j ] + 1 ) * ( g [ i + 1 ][ j + 1 ] + 1 );
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
public :
int countSubstrings ( string s , string t ) {
int ans = 0 ;
int m = s . length (), n = t . length ();
int f [ m + 1 ][ n + 1 ];
int g [ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof ( f ));
memset ( g , 0 , sizeof ( g ));
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( s [ i ] == t [ j ]) {
f [ i + 1 ][ j + 1 ] = f [ i ][ j ] + 1 ;
}
}
}
for ( int i = m - 1 ; i >= 0 ; -- i ) {
for ( int j = n - 1 ; j >= 0 ; -- j ) {
if ( s [ i ] == t [ j ]) {
g [ i ][ j ] = g [ i + 1 ][ j + 1 ] + 1 ;
} else {
ans += ( f [ i ][ j ] + 1 ) * ( g [ i + 1 ][ j + 1 ] + 1 );
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 func countSubstrings ( s string , t string ) ( ans int ) {
m , n := len ( s ), len ( t )
f := make ([][] int , m + 1 )
g := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , n + 1 )
g [ i ] = make ([] int , n + 1 )
}
for i , a := range s {
for j , b := range t {
if a == b {
f [ i + 1 ][ j + 1 ] = f [ i ][ j ] + 1
}
}
}
for i := m - 1 ; i >= 0 ; i -- {
for j := n - 1 ; j >= 0 ; j -- {
if s [ i ] == t [ j ] {
g [ i ][ j ] = g [ i + 1 ][ j + 1 ] + 1
} else {
ans += ( f [ i ][ j ] + 1 ) * ( g [ i + 1 ][ j + 1 ] + 1 )
}
}
}
return
}
GitHub