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 "computer"
and "computation"
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: ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba", "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: ("ab", "bb") ("ab", "bb") ("ab", "bb") The underlined portions are the substrings that are chosen from s and t.
Example 3:
Input: s = "a", t = "a" Output: 0
Example 4:
Input: s = "abe", t = "bbc" Output: 10
Constraints:
1 <= s.length, t.length <= 100
s
andt
consist of lowercase English letters only.
Solution1: All Pairs + Prefix Matching
match s[i:i+p] with t[j:j+p], is there is one missed char, increase the ans, until there are two miss matched chars or reach the end.
Time complexity: O(m*n*min(m,n))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int countSubstrings(string s, string t) { const int m = s.length(); const int n = t.length(); int ans = 0, diff = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j, diff = 0) for (int p = 0; i + p < m && j + p < n && diff <= 1; ++p) if ((diff += (s[i + p] != t[j + p])) == 1) ++ans; return ans; } }; |
Solution 2: Continuous Matching
Start matching s[0] with t[j] and s[i] with t[0]
Time complexity: O(mn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int countSubstrings(string s, string t) { const int m = s.length(); const int n = t.length(); int ans = 0; auto helper = [&](int i, int j) { for (int cur = 0, pre = 0; i < m && j < n; ++i, ++j) { ++cur; if (s[i] != t[j]) { pre = cur; cur = 0; } ans += pre; } }; for (int i = 0; i < m; ++i) helper(i, 0); for (int j = 1; j < n; ++j) helper(0, j); return ans; } }; |