You get a string s and a string t.
Return how many ways you can delete letters from s so that t is left.
The letters you keep stay in their order. Two ways are different when they keep different positions of s.
The count can have hundreds of digits, so return it modulo 1,000,000,007.
Example 1:
Input: s = "banana", t = "ban" Output: 3 Explanation: Position 0 holds the only b. The a can be the one at 1 or the one at 3. The n must come after that a. So the kept positions are [0,1,2], [0,1,4] or [0,3,4].
Example 2:
Input: s = "llama", t = "lama" Output: 2 Explanation: Delete the first l or the second l. Either way, lama is left.
Example 3:
Input: s = "cat", t = "tac" Output: 0 Explanation: s has the same letters in another order. Deleting letters never changes the order of the rest.
Constraints:
shas 1 to 1,000 letters.thas 1 to 1,000 letters.- All letters are lowercase English letters.
Note:
Your solution should run in O(m · n) time. Here m and n are the lengths of s and t.
Trying every set of letters to keep is far too slow. Count with a table instead. Let
ways[j] be the number of ways to make the first j letters of t, using only the letters of s read so far. At the start, ways[0] is 1: deleting everything leaves the empty start of t. Every other entry starts at 0. Here n is the length of t, and the answer is ways[n] after the last letter of s.
Read
s one letter at a time. When the letter equals t[j - 1], it can end any way of making the first j - 1 letters. So ways[j] grows by ways[j - 1].Go over
j from n down to 1. Then ways[j - 1] still holds its count from before this letter, and no letter of s is used twice in one way. Going up would let the one m of "lemon" make "mm".
Each of the
m letters of s goes over the n entries: O(m · n) time. The table holds n + 1 numbers: O(n) extra space.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
