Re: [閒聊] 每日leetcode

[sixB (6B)]

1639.

破防  大家都去跨年開趴了嗎

這題竟然都沒人發

hard難得好寫的dp欸==

先算frequency

然後dp一個一個推

開2d的話j就不用倒著計算了

記得要mod

using ll = long long;
class Solution {
public:
    ll mod = 1e9 + 7;
    int numWays(vector<string>& words, string target) {
        int len = words[0].length();
        int tlen = target.length();
        vector<vector<ll>> ch(len, vector<ll>(26, 0));
        for(int i = 0; i < len; i++){
            for(auto& s: words){
                ch[i][s[i]-'a']++;
            }
        }
        ll res = 0;
        vector<ll> dp(tlen, 0);
        for(int i = 0; i < len; i++){
            for(int j = min(i, tlen-1); j > 0; j--){
                ll add = (dp[j-1] * ch[i][target[j]-'a']) % mod;
                dp[j] += add;
                dp[j] %= mod;
            }
            dp[0] += ch[i][target[0]-'a'];
            dp[0] %= mod;

        }
        return dp.back();
    }
};
-----
Sent from JPTT on my iPad

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735497008.A.CC5.html
→ DJYOMIYAHINA: 對不起