Count number of texts

Hash Table Math String Dynamic Programming

49.9% acceptance

Feb 25, 2026

940

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 "222662". 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_texts(pressed_keys: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let bytes = pressed_keys.as_bytes();
    let n = bytes.len();
    let mut dp = vec![0i64; n + 1];
    dp[0] = 1;
    for i in 0..n {
      let d = bytes[i];
      let max_press = if d == b'7' || d == b'9' { 4 } else { 3 };
      // Try ending groups of size 1..=max_press
      for k in 1..=max_press {
        if i + 1 < k { break; }
        // Check all bytes[i+1-k..=i] are the same as d
        if bytes[i + 1 - k] == d {
          dp[i + 1] = (dp[i + 1] + dp[i + 1 - k]) % MOD;
        } else {
          break;
        }
      }
    }
    dp[n] as i32
  }
}