940. Distinct Subsequences II

LeetCode hard оригинал: C# #array #csharp #dynamic-programming #hard #leetcode #matrix #string

LeetCode Static

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"

Output: 7

C# решение

сопоставлено/оригинал

public class Solution {
    private const int MOD = 1000000007;
    
    public int CountSubsequences(string s) {
        int[] dp = new int[26];
        foreach (char c in s) {
            int index = c - 'a';
            dp[index] = (dp.Sum() + 1) % MOD;
        }
        return dp.Sum() % MOD;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private const int MOD = 1000000007;
    
    public int CountSubsequences(string s) {
        vector<int>& dp = new int[26];
        foreach (char c in s) {
            int index = c - 'a';
            dp[index] = (dp.Sum() + 1) % MOD;
        }
        return dp.Sum() % MOD;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    private static final int MOD = 1000000007;
    
    public int countSubsequences(String s) {
        int[] dp = new int[26];
        for (char c : s.toCharArray()) {
            int index = c - 'a';
            dp[index] = (int)(((long)sum(dp) + 1) % MOD);
        }
        return sum(dp);
    }
    
    private int sum(int[] dp) {
        int result = 0;
        for (int val : dp) {
            result = (result + val) % MOD;
        }
        return result;
    }
}

Python решение

сопоставлено/оригинал

MOD = 10**9 + 7

def countSubsequences(s):
    dp = [0] * 26
    for c in s:
        index = ord(c) - ord('a')
        dp[index] = (sum(dp) + 1) % MOD
    return sum(dp) % MOD

Go решение

сопоставлено/оригинал

package main

const MOD = 1000000007

func countSubsequences(s string) int {
    dp := make([]int, 26)
    for _, c := range s {
        index := c - 'a'
        sum := 0
        for _, val := range dp {
            sum = (sum + val) % MOD
        }
        dp[index] = (sum + 1) % MOD
    }
    result := 0
    for _, val := range dp {
        result = (result + val) % MOD
    }
    return result
}

Algorithm

Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

Инициализировать матрицу DP нулями.

Пройти по каждому символу строки:

Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ.

Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений.

Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.