Class Solution
java.lang.Object
g1601_1700.s1638_count_substrings_that_differ_by_one_character.Solution
1638 - Count Substrings That Differ by One Character.<p>Medium</p>
<p>Given two strings <code>s</code> and <code>t</code>, find the number of ways you can choose a non-empty substring of <code>s</code> and replace a <strong>single character</strong> by a different character such that the resulting substring is a substring of <code>t</code>. In other words, find the number of substrings in <code>s</code> that differ from some substring in <code>t</code> by <strong>exactly</strong> one character.</p>
<p>For example, the underlined substrings in <code>"computer"</code> and <code>"computation"</code> only differ by the <code>'e'</code>/<code>'a'</code>, so this is a valid way.</p>
<p>Return <em>the number of substrings that satisfy the condition above.</em></p>
<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> s = “aba”, t = “baba”</p>
<p><strong>Output:</strong> 6</p>
<p><strong>Explanation:</strong> The following are the pairs of substrings from s and t that differ by exactly 1 character:</p>
<p>(“aba”, “baba”)</p>
<p>(“aba”, “baba”)</p>
<p>(“aba”, “baba”)</p>
<p>(“aba”, “baba”)</p>
<p>(“aba”, “baba”)</p>
<p>(“aba”, “baba”)</p>
<p>The underlined portions are the substrings that are chosen from s and t.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> s = “ab”, t = “bb”</p>
<p><strong>Output:</strong> 3</p>
<p><strong>Explanation:</strong> The following are the pairs of substrings from s and t that differ by 1 character:</p>
<p>(“ab”, “bb”)</p>
<p>(“ab”, “bb”)</p>
<p>(“ab”, “bb”)</p>
<p>The underlined portions are the substrings that are chosen from s and t.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= s.length, t.length <= 100</code></li>
<li><code>s</code> and <code>t</code> consist of lowercase English letters only.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
countSubstrings
-