请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目
1. 回溯+标记
每一趟跑一个青蛙（超时）
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n =croakOfFrogs.size();
string pattern = "croak";
if(n%pattern.size()!=0) return -1;
vector<bool> visit(n);
int count = 0;
for(int i=0;i<n;i++){
if(!visit[i]&&croakOfFrogs[i]==pattern[0]){
if(backtrack(croakOfFrogs,pattern,visit,i)==0) return -1;
count++;
}
}
return count;
}
bool backtrack(string& s,string &pattern,vector<bool>&visit,int i){
if(i==s.size()) return true;
int j = 0;
while(i<s.size()&&j<pattern.size()){
if(!visit[i]&&s[i]==pattern[j]){
visit[i] = true;
i++;
j++;
}
else i++;
}
if(j==pattern.size()){//当前匹配完毕
return backtrack(s,pattern,visit,i);
}
if(j==0) return true;//该青蛙终止
return false;//没叫完
}
};
2. 循环队列
一趟跑一只青蛙（超时）
class Solution {
public:
int minNumberOfFrogs(string mainstr) {
int n = mainstr.size();
string pattern = "croak";
if(n%pattern.size()!=0) return -1;
int count = 0;
queue<char> q;
for(int i=0;i<n;i++)
q.push(mainstr[i]);
int index = 0;//匹配串指针，循环移动
while(!q.empty()){
int len = q.size();
if(q.front()!=pattern[0]) return -1;//第一个字符必须与模板串相同
count++;//一趟青蛙叫
for(int i=0;i<len;i++){
char c = q.front();
q.pop();
if(c==pattern[index]){
index = (index + 1)%pattern.size();
}
else q.push(c);//送到第二轮
}
if(index!=0) return -1;//必须完全匹配
}
return count;
}
};
3. 哈希计数
记录上一个状态的数量，以此转移到下一个状态
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n = croakOfFrogs.size();
if(n%5!=0) return -1;
map<char,char> pre;
const string croak = "croakc";
for (int i = 1; i < croak.size(); i++)
pre[croak[i]] = croak[i - 1];
map<char,int> cnt;
for (char &ch: croakOfFrogs) {
char pr = pre[ch]; // pre 为 ch 在 "croak" 中的上一个字母
if (cnt[pr]) // 如果有青蛙发出了 pre 的声音
cnt[pr]--; // 复用一只
else if (ch != 'c') // 否则青蛙必须从 'c' 开始蛙鸣
return -1; // 不符合要求
cnt[ch]++; // 发出了 ch 的声音
}
if (cnt['c'] || cnt['r'] || cnt['o'] || cnt['a'])
return -1; // 有发出其它声音的青蛙，不符合要求
return cnt['k']; // 最后青蛙们都发出了 'k' 的声音
}
};