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/