class Solution { public int distinctSubseqII(String s) { int MOD = (int)1e9+7; int res = 0; int[] f = new int[26]; for (int i = 0; i < s.length(); i++) { int cur = s.charAt(i) - 'a', pre = f[cur]; f[cur] = (res + 1) % MOD; res = ((res + f[cur] - pre) % MOD + MOD) % MOD; } return res; } }
class Solution { public: int distinctSubseqII(string s) { int MOD = (int)1e9+7; int res = 0; int f[26]; memset(f, 0, sizeof(f)); for (int i = 0; i < s.size(); i++) { int cur = s[i] - 'a', pre = f[cur]; f[cur] = (res + 1) % MOD; res = ((res + f[cur] - pre) % MOD + MOD) % MOD; } return res; } };
impl Solution { pub fn distinct_subseq_ii(s: String) -> i32 { let MOD = 1000000007; let mut res = 0; let mut f = vec![0; 26]; for cur in s.chars() { let i = cur as u8 - 'a' as u8; let pre = f[i as usize]; f[i as usize] = (res + 1) % MOD; res = ((res + f[i as usize] - pre) % MOD + MOD) % MOD; } res } }
栗子【vonvv】:
当前遍历字符 | f[i] | 子串 |
---|---|---|
v | 1 | v |
o | 2 | vo,o |
n | 4 | vn,von,on,n |
v | 8 | vv,vov,ov,vnv,vonv,onv,nv,v |
v | 15 | vv,vov,ov,vnv,vonv,onv,nv,vvv,vovv,ovv,vnvv,vonvv,onvv,nvv,vv,v |
最终即为三个字符对应值相加f[o]+f[n]+f[v]=2+4+15=21
注意!!!
因为要计算sum(f),这值可能会超级大,所以要用long型!
class Solution { public int distinctSubseqII(String s) { int MOD = (int)1e9+7; long[] f = new long[26]; for (char cur : s.toCharArray()) { f[cur - 'a'] = Arrays.stream(f).sum() % MOD + 1; } return (int)(Arrays.stream(f).sum() % MOD); } }
class Solution { public: int distinctSubseqII(string s) { int MOD = (int)1e9+7; vector<long> f(26, 0); for (auto cur : s) { f[cur - 'a'] = accumulate(f.begin(), f.end(), 1l) % MOD; } return accumulate(f.begin(), f.end(), 0l) % MOD; } };
impl Solution { pub fn distinct_subseq_ii(s: String) -> i32 { let MOD = 1000000007; let mut f = vec![0; 26]; for cur in s.chars() { f[(cur as u8 - 'a' as u8) as usize] = f.iter().sum::<i64>() % MOD + 1; } (f.iter().sum::<i64>() % MOD) as i32 } }
完全没思路的一道题~是那种望而生畏,读完题失去梦想,看完题解觉得自己是傻子的类型……
看普通动规的题解感觉好难理解,差点放弃,然后跳到后面理清思路返回来就好理解很多,但还是只选了两种比较简洁的方式写;