Count Number of Texts — LeetCode 2266 Python Solution

The problem

Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

Example

Input

pressedKeys = "22233"

Output

8

Explanation

The possible text messages Alice could have sent are:

Python solution

mod = 10**9 + 7
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(100000):
    f.append((f[-1] + f[-2] + f[-3]) % mod)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % mod)


class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for c, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if c in "79" else f[m]) % mod
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2266. Count Number of Texts is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems