Rust 力扣 - 2266. 统计打字方案数

题目描述

题解思路

这题可以先求按了多少次相同连续的按钮，所有的连续相同按钮表示的方案数的乘积就是本题答案

我们的关键问题就转换成了按n个连续相同按钮表示的方案数

设f(i)表示按i个连续相同按钮表示的方案数

• 如果按钮是三个字符的
  f(i) = f(i - 1) + f(i - 2) + f(i - 3)
• 如果按钮是四个字符的
  f(i) = f(i - 1) + f(i - 2) + f(i - 3) + f(i - 4)

题解代码

impl Solution {pub fn count_texts(pressed_keys: String) -> i32 {let pressed_keys = pressed_keys.as_bytes();let n = pressed_keys.len();let mut f3 = vec![0; (n + 1).max(5)];let mut f4 = vec![0; (n + 1).max(5)];(f3[1], f3[2], f3[3], f3[4], f4[1], f4[2], f4[3], f4[4]) = (1, 2, 4, 7, 1, 2, 4, 8);for i in 5..=n {f3[i] = (f3[i - 1] + f3[i - 2] + f3[i - 3]) % 1000000007;f4[i] = (f4[i - 1] + f4[i - 2] + f4[i - 3] + f4[i - 4]) % 1000000007;}let mut c = 1;let mut ans = 1usize;for i in 1..n {if pressed_keys[i] == pressed_keys[i - 1] {c += 1;} else {match pressed_keys[i - 1] {b'7' | b'9' => {ans *= f4[c];}_ => {ans *= f3[c];}}c = 1;ans %= 1000000007;}}match pressed_keys[n - 1] {b'7' | b'9' => {ans *= f4[c];}_ => {ans *= f3[c];}}(ans % 1000000007) as i32}
}

题目链接

https://leetcode.cn/problems/count-number-of-texts/