题解 | #好多牛牛#
好多牛牛
http://www.nowcoder.com/practice/edced5e80f3e46efa9c965e7f634c58c
题意
长度为n的字符串中，有多少个子串为niuniu
其中 n≤105
对结果模1e9+7
算法
深度搜索
dfs(stringidx,niuniuidx)
深度搜索函数，接受当前搜索到的字符串的长度的下标，和niuniu当前匹配到的下标
每次从string的当前位置遍历i in range(stringidx,n)到字符串尾部，如果和要匹配的niuniu 的 下标字符一致，那么递归dfs(i+1,niuniuidx+1)
代码
class Solution:
s = ""
# 递归搜索， 字符串搜索的下标， niuniu匹配的下标
def dfs(self, stringidx, niuniuidx):
if niuniuidx == 6: # 完全匹配则返回1 否则返回0
return 1;
if stringidx == len(self.s):
return 0;
cnt = 0 # 统计方案数
for i in range(stringidx, len(self.s)): # 从字符串下标向后搜索 尝试匹配 niuniu下标当前位置的字符
if "niuniu"[niuniuidx] == self.s[i]:
cnt += self.dfs(i+1,niuniuidx+1) # 如果匹配，递归尝试下一个位置
return cnt
def solve(self , s ):
self.s = s
return self.dfs(0,0) % 1000000007
复杂度分析
时间复杂度: 我们每一层遍历字符串，都需要O(n), 一共6层，所以总复杂度为 O(n6) 无法在要求时间内完成
空间复杂度: 我们的空间消耗在递归的内存上，因此和递归的深度相关，注意到递归的深度受到niuniuidx控制，最大为6，所以空间复杂度为O(1)
遍历递推
假设题目不是要求子串，而是连续的，那么枚举每一个位置，检查从这个位置开始是不是"niuniu" 即可
但是这里要是子串，也就是来源的字符可能处于不连续的位置，那么我们考虑 逐个匹配"niuniu" 字符串，记录到当前位置，匹配到每一位的分别有多少种方案
stateCnt[i] 表示已经匹了i个字符的方案数
那么 如果 当前位置是的字符是 'n' 则 stateCnt[1]+=stateCnt[0],stateCnt[4]+=stateCnt[3], 也就是原来匹配0个(未匹配任何字符)和匹配了3个(匹配了'niu')的，现在多匹配了一个牛
以 样例 为例
stateCnt | 默认状态 | n | i | u | n | i | n | i | u |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1(n) | 0 | 0+1=1 | 1 | 1 | 1+1=2 | 2 | 2+1=3 | 3 | 3 |
| 2(n i) | 0 | 0 | 0+1=1 | 1 | 1 | 1+2=3 | 3 | 3+3=6 | 6 |
| 3(ni u) | 0 | 0 | 0 | 0+1=1 | 1 | 1 | 1 | 1 | 1+6=7 |
| 4(niu n) | 0 | 0+0=0 | 0 | 0 | 0+1=1 | 1 | 1+1=2 | 2 | 2+1=3 |
| 5(niun i) | 0 | 0 | 0+0=0 | 0 | 0 | 0+1=1 | 1 | 1+2=3 | 3+2=5 |
| 6(niuni u) | 0 | 0 | 0 | 0+0=0 | 0 | 0 | 0 | 0 | 0+3=3 (返回值) |
代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param s string字符串
* @return int整型
*/
int solve(string s) {
const int mod = 1000000007;
vector<int> stateCnt = {1,0,0,0,0,0,0}; // 匹配的状态分别是 匹配0个1个2个3个4个5个6个 对应的方案数
int n = s.length();
for(int i=0;i<n;i++){
if(s[i] == 'n'){ // 匹配到n的状态计数转移
(stateCnt[1]+=stateCnt[0])%=mod;
(stateCnt[4]+=stateCnt[3])%=mod;
}else if(s[i] == 'i'){ // 匹配到i的状态计数转移
(stateCnt[2]+=stateCnt[1])%=mod;
(stateCnt[5]+=stateCnt[4])%=mod;
}else if(s[i] == 'u'){ // 匹配到u的状态计数转移
(stateCnt[3]+=stateCnt[2])%=mod;
(stateCnt[6]+=stateCnt[5])%=mod;
}
}
return stateCnt[6];
}
};
复杂度分析
时间复杂度: 我们遍历字符串每一位，每次状态常数代价转移，所以总复杂度为 O(n)
空间复杂度: 除了临时变量，我们只用了一个常数大小的state数组来记录，遍历过程中的方案数，空间复杂度为 O(1)
知识点
- 遍历递推, 我们在递推过程中，表达式为stateCnt[状态]=方法数
查看9道真题和解析
