子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。
为了防止答案过大,答案对1e9+7取模
考虑通用的问题,给定一个字符串S和模式串T,求S中有多少个子序列=T。
const int mod = 1e9+7; const string pat = "niuniu"; class Solution { public: /** * 好多牛牛 * @param s string字符串 * @return int整型 */ int solve(string& s) { // write code here int pLen = pat.size(); vector<int> dp(pLen+1); dp[0] = 1; for(const auto& c:s){ for(int j=pLen-1;j>=0;j--){ if(c==pat[j]){ dp[j+1] = (dp[j+1] + dp[j])%mod; } } } return dp[pLen]; } };
const int mod = 1e9+7; class Solution { public: /** * 好多牛牛 * @param s string字符串 * @return int整型 */ int solve(string& s) { // write code here int sLen = s.size(); vector<int> dp(5); for(int i=0;i<sLen;i++){ switch(s[i]){ case 'n': dp[0] = (dp[0]+1)%mod; dp[3] = (dp[3]+dp[2])%mod;break; case 'i': dp[1] = (dp[0]+dp[1])%mod; dp[4] = (dp[3]+dp[4])%mod;break; case 'u': dp[2] = (dp[1]+dp[2])%mod; dp[5] = (dp[4]+dp[5])%mod;break; default: break; } } return dp[5]; } };
class Solution { public: /** * 好多牛牛 * @param s string字符串 * @return int整型 */ int solve(string s) { string t = "niuniu"; int M = 1e9+7, n=s.length(), m=t.length(); long dp[n]; memset(dp, 0, sizeof(dp)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(s[i]==t[j]){ dp[j] += (j==0 ? 1 : dp[j-1]); dp[j] %= M; } return dp[m-1]; } };
int solve(string s) { const int MOD = 1e9 + 7; string str = "niuniu"; vector<vector<long long>> dp(s.size(),vector<long long>(str.size(),0)); for(int i=0;i<s.size();i++){ for(int j=0;j<str.size();j++){ if(j == 0){ if(s[i] == str[j]){ dp[i][j] = 1; } }else{ if(s[i] == str[j]){ for(int k=0;k<i;k++){ dp[i][j] += dp[k][j-1]; dp[i][j] %= MOD; } } } } } long long res = 0; for(int i=0;i<s.size();i++){ res += dp[i][str.size()-1]; res %= MOD; } return res; }这样写发现超时了,看了别人的代码后,才发现不需要二维的dp,因为说给的字符串比较特殊,没有aa这种两个同样的字符相连的情况,所以可以不用记录原始字符串的结尾,代码改为了下面这样。
int solve(string s) { const int MOD = 1e9 + 7; string str = "niuniu"; vector<long long> dp(str.size(),0); for(int i=0;i<s.size();i++){ for(int j=0;j<str.size();j++){ if(s[i] == str[j]){ if(j == 0){ dp[j]++; dp[j] %= MOD; }else{ dp[j] += dp[j-1]; dp[j] %= MOD; } } } } return dp[str.size()-1]; }
class Solution { public: int solve(string s) { int count[6] = { 0,0,0,0,0,0 }; //分别记录已遍历序列中"n","ni","niu","niun","niuni","niuniu"的个数 for (int i = 0; i < s.size(); ++i) { switch (s[i]) { case 'n':++count[0]; count[3] += count[2]; count[0] %= 1000000007; count[3] %= 1000000007; break; //当前字符是'n'时,"n"与"niun"数量改变 case 'i':count[1] += count[0]; count[4] += count[3]; count[1] %= 1000000007; count[4] %= 1000000007; break; //当前字符是'i'时,"ni"与"niuni"数量改变 case 'u':count[2] += count[1]; count[5] += count[4]; count[2] %= 1000000007; count[5] %= 1000000007; break; //当前字符是'u'时,"niu"与"niuniu"数量改变 } } return count[5]; } };
memset(f, 0, sizeof(f)); f[0] = 1; string a = "*niuniu"; for(int i = 1; i <= s.size(); i++){ for(int j = 1; j <= 6; j++){ if(s[i-1] == a[j]){ f[j] += f[j-1]; f[j] %= MOD; } } } return f[6];
1 1 1 1 1 1 1 1 1 1 * 1 1 1 2 2 3 3 3 0 0 n 0 1 1 1 3 3 6 6 0 0 i 0 0 1 1 1 1 1 7 0 0 u 0 0 0 1 1 2 2 2 0 0 n 0 0 0 0 1 1 3 3 0 0 i 0 0 0 0 0 0 0 3 0 0 u n i u n i n i u
令dp数组为主串s的长度为i的前缀s[0, i]中和模式串pat("niuniu")任意长度前缀匹配的数目
那么状态转移方程即为
dp[j] += dp[j - 1] if s[i] == pat[j]
其中当j = 0时,dp[0] += 1, 不妨在dp[0]的前面插入一个1, 以使代码更加整洁
int solve(string s) { // write code here int n = s.size(); if(n < 6) return 0; string pat = "niuniu"; size_t plen = pat.size(); vector<int> dp(plen + 1, 0); dp[0] = 1; for(int i = 0; i < n; ++i) { for(int j = 0; j < plen; ++j) { if(s[i] == pat[j]) dp[j + 1] += dp[j]; dp[j + 1] %= 1000000007; } } return dp[plen]; }
import java.util.*; public class Solution { /** * 好多牛牛 * @param s string字符串 * @return int整型 */ public int solve (String s) { String niu = "niuniu"; int n = s.length(); int m = niu.length(); int mo = 1000000007; int[] dp = new int[m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s.charAt(i) == niu.charAt(j)){ dp[j] += (j==0 ? 1 : dp[j-1]); dp[j] %= mo; } } } return dp[m-1]; } }
public class Solution { /** * 好多牛牛 * @param s string字符串 * @return int整型 */ public int solve (String s) { // write code here int M = 1000000007; String t = "niuniu"; int m = s.length(); int n = t.length(); int[][] dp = new int[n+1][m+1]; for(int j = 0; j <= m;j++){ dp[0][j] = 1; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(s.charAt(j-1) == t.charAt(i-1)){ dp[i][j] = dp[i-1][j-1] + dp[i][j-1]; dp[i][j] %= M; }else{ dp[i][j] = dp[i][j-1] % M; } } } return dp[n][m]%M; } }
class Solution: def solve(self, s): re = [0 for _ in range(6)] for i in s: if i == 'n': re[0] = (re[0] + 1) % (1e9 + 7) re[3] = (re[2] + re[3]) % (1e9 + 7) if i == 'i': re[1] = (re[0] + re[1]) % (1e9 + 7) re[4] = (re[3] + re[4]) % (1e9 + 7) if i == 'u': re[2] = (re[1] + re[2]) % (1e9 + 7) re[5] = (re[4] + re[5]) % (1e9 + 7) return re[5]