当前位置：首页 > article >正文

美团2024秋招编程题：小美的red子序列数量之和

article 2024/9/21 1:49:15

题目为：

小美有一个字符串，小美想知道这个字符串的所有连续子串中，red 子序列的数量之和。
子串是指从原字符串中，连续的选择一段字符组成的新字符串。
定义 red 子序列为从原字符串中从左到右依次取出r、e和d组成的新字符串。

输入描述

第一行输入一个长度不超过10^5、且仅由小写字母构成的字符串s，代表小美的字符串。

输出描述

在一行上输出一个整数，代表所有子串中 red 子序列的数量之和。由于答案可能很大，请将答案对(10^9十7)取模后输出。

示例 1
输入

redd

输出

3

说明

在 red 子串中，有1个red 子序列;
在 redd 子串中，有 2个red 子序列:

接替代码：

def count_red_subsequences(s):
    MOD = 10**9 + 7
    n = len(s)
    
    
    red_count = 0
    for j in range(n-2):
        dp = [[0] * 3 for _ in range(n)]
        for i in range(j, n):
            if s[i] == 'r':
                dp[i][0] = 1 + (dp[i-1][0] if i > 0 else 0)
            if s[i] == 'e':
                if i > 0:
                    dp[i][1] = dp[i-1][1] + dp[i-1][0]
            if s[i] == 'd':
                if i > 0:
                    dp[i][2] = dp[i-1][2] + dp[i-1][1]
            if i > 0:
                # dp[i][0] = (dp[i][0] + dp[i-1][0]) % MOD
                dp[i][2] = (dp[i][2] + dp[i-1][2]) % MOD
            if s[i] == 'd':
                red_count = (red_count + dp[i][2]) % MOD
    
    return red_count

题解

dp[i][0]表示以第i个字符结尾的子串钟r的数量
dp[i][1]表示以第i个字符结尾的子串钟re的数量
dp[i][2]表示以第i个字符结尾的子串钟red的数量

两层for循环遍历，计算第j个字符开始第i个字符结尾的子串钟，red子序列的全部数量。
dp[i][2] = (dp[i][2] + dp[i-1][2]) % MOD重点是这句计算了s[j:i]中，s[j:i-1]中red子序列加上s[j:i]中red子序列之和。这样就成功计算了所有连续子串中的red子序列之和。