2266. Count Number of Texts

Description

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

In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.

• For example, to add the letter 's', Alice has to press '7' four times. Similarly, to add the letter 'k', Alice has to press '5' twice.
• Note that the digits '0' and '1' do not map to any letters, so Alice does not use them.

However, due to an error in transmission, Bob did not receive Alice's text message but received a string of pressed keys instead.

• For example, when Alice sent the message "bob", Bob received the string "2266622".

Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: pressedKeys = "22233"
Output: 8
Explanation:
The possible text messages Alice could have sent are:
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce".
Since there are 8 possible messages, we return 8.

Example 2:

Input: pressedKeys = "222222222222222222222222222222222222"
Output: 82876089
Explanation:
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.

 

Constraints:

• 1 <= pressedKeys.length <= 105
• pressedKeys only consists of digits from '2' - '9'.

Solutions

Solution 1: Grouping + Dynamic Programming

According to the problem description, for consecutive identical characters in the string $\textit{pressedKeys}$, we can group them together and then calculate the number of ways for each group. Finally, we multiply the number of ways for all groups.

The key problem is how to calculate the number of ways for each group.

If a group of characters is '7' or '9', we can consider the last $1$, $2$, $3$, or $4$ characters of the group as one letter, then reduce the size of the group and transform it into a smaller subproblem.

Similarly, if a group of characters is '2', '3', '4', '5', '6', or '8', we can consider the last $1$, $2$, or $3$ characters of the group as one letter, then reduce the size of the group and transform it into a smaller subproblem.

Therefore, we define $f[i]$ to represent the number of ways for a group of length $i$ with identical characters that are not '7' or '9', and $g[i]$ to represent the number of ways for a group of length $i$ with identical characters that are '7' or '9'.

Initially, $f[0] = f[1] = 1$, $f[2] = 2$, $f[3] = 4$, $g[0] = g[1] = 1$, $g[2] = 2$, $g[3] = 4$.

For $i \ge 4$, we have:

$$ \begin{aligned} f[i] & = f[i-1] + f[i-2] + f[i-3] \ g[i] & = g[i-1] + g[i-2] + g[i-3] + g[i-4] \end{aligned} $$

Finally, we traverse $\textit{pressedKeys}$, group consecutive identical characters, calculate the number of ways for each group, and multiply the number of ways for all groups.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $\textit{pressedKeys}$.

Python3JavaC++Go

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

class Solution {
    private static final int N = 100010;
    private static final int MOD = (int) 1e9 + 7;
    private static long[] f = new long[N];
    private static long[] g = new long[N];
    static {
        f[0] = f[1] = 1;
        f[2] = 2;
        f[3] = 4;
        g[0] = g[1] = 1;
        g[2] = 2;
        g[3] = 4;
        for (int i = 4; i < N; ++i) {
            f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD;
            g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % MOD;
        }
    }

    public int countTexts(String pressedKeys) {
        long ans = 1;
        for (int i = 0, n = pressedKeys.length(); i < n; ++i) {
            char c = pressedKeys.charAt(i);
            int j = i;
            while (j + 1 < n && pressedKeys.charAt(j + 1) == c) {
                ++j;
            }
            int cnt = j - i + 1;
            ans = c == '7' || c == '9' ? ans * g[cnt] : ans * f[cnt];
            ans %= MOD;
            i = j;
        }
        return (int) ans;
    }
}

const int mod = 1e9 + 7;
const int n = 1e5 + 10;
long long f[n], g[n];

int init = []() {
    f[0] = g[0] = 1;
    f[1] = g[1] = 1;
    f[2] = g[2] = 2;
    f[3] = g[3] = 4;
    for (int i = 4; i < n; ++i) {
        f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % mod;
        g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % mod;
    }
    return 0;
}();

class Solution {
public:
    int countTexts(string pressedKeys) {
        long long ans = 1;
        for (int i = 0, n = pressedKeys.length(); i < n; ++i) {
            char c = pressedKeys[i];
            int j = i;
            while (j + 1 < n && pressedKeys[j + 1] == c) {
                ++j;
            }
            int cnt = j - i + 1;
            ans = c == '7' || c == '9' ? ans * g[cnt] : ans * f[cnt];
            ans %= mod;
            i = j;
        }
        return ans;
    }
};

const mod int = 1e9 + 7
const n int = 1e5 + 10

var f = [n]int{1, 1, 2, 4}
var g = f

func init() {
    for i := 4; i < n; i++ {
        f[i] = (f[i-1] + f[i-2] + f[i-3]) % mod
        g[i] = (g[i-1] + g[i-2] + g[i-3] + g[i-4]) % mod
    }
}

func countTexts(pressedKeys string) int {
    ans := 1
    for i, j, n := 0, 0, len(pressedKeys); i < n; i++ {
        c := pressedKeys[i]
        j = i
        for j+1 < n && pressedKeys[j+1] == c {
            j++
        }
        cnt := j - i + 1
        if c == '7' || c == '9' {
            ans = ans * g[cnt] % mod
        } else {
            ans = ans * f[cnt] % mod
        }
        i = j
    }
    return ans
}

Comments