Re: [閒聊] 每日leetcode
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
→
12/30 09:01,
11月前
, 1F
12/30 09:01, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1229 之 1554 篇)：