LeetCode Biweekly Contest 38 4問目 - Number of Ways to Form a Target String Given a Dictionary [1639]

Source

LeetCode Biweekly Contest 38
問題文

問題概要

省略

解法

省略

cLay（version 20201031-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

Modint cnt[1001][26];
Modint dp[1001], nx[1001];

class Solution {
public:
  int numWays(vector<string>& S, string T) {
    int N = S.size(), M = S[0].size();
    Modint s;
    
    rep(i,N) rep(j,M) S[i][j] -= 'a';
    rep(i,T.size()) T[i] -= 'a';

    rep(i,M) rep(j,26) cnt[i][j] = 0;
    rep(i,N) rep(j,M) cnt[j][S[i][j]] += 1;
    
    rep(i,M+1) dp[i] = 0;
    dp[0] = 1;

    rep(k,T.size()){
      (dp[0], s) = (0, dp[0]);
      rep(i,M) (dp[i+1], s) = (s * cnt[i][T[k]], s + dp[i+1]);
    }
    return sum(dp(M+1));
  }
};

Current time: 2024年04月25日07時45分51秒
Last modified: 2020年11月01日01時36分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)