【模拟】数⻘蛙（medium）

题⽬链接：1419. 数⻘蛙

题⽬描述：

给你⼀个字符串 croakOfFrogs，它表⽰不同⻘蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同⼀时间可以有多只⻘蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同⻘蛙的最少数⽬。
要想发出蛙鸣 “croak”，⻘蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字⺟。如果没有输出全部五个字⺟，那么它就不会发出声⾳。如果字符串 croakOfFrogs 不是由若⼲有效的"croak" 字符混合⽽成，请返回 -1 。
⽰例 1：
输⼊：croakOfFrogs = “croakcroak”
输出：1
解释：⼀只⻘蛙 “呱呱” 两次
⽰例 2：
输⼊：croakOfFrogs = “crcoakroak”
输出：2
解释：最少需要两只⻘蛙，“呱呱” 声⽤⿊体标注
第⼀只⻘蛙 “crcoakroak”
第⼆只⻘蛙 “crcoakroak”
⽰例 3：
输⼊：croakOfFrogs = “croakcrook”
输出：-1
解释：给出的字符串不是 “croak” 的有效组合。
提⽰：
1 <= croakOfFrogs.length <= 105
字符串中的字符只有 ‘c’, ‘r’, ‘o’, ‘a’ 或者 ‘k’

解法（模拟 + 分情况讨论）

算法思路：

模拟⻘蛙的叫声。
◦ 当遇到 ‘r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，
有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有，
直接返回 -1 ；
◦ 当遇到 ‘c’ 这个字符的时候，我们去看看 ‘k’ 这个字符有没有⻘蛙叫出来。如果有，就让
这个⻘蛙继续去喊 ‘c’ 这个字符；如果没有的话，就重新搞⼀个⻘蛙。

算法代码：

class Solution{public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n]; // 数组模拟哈希表Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标]for(int i = 0; i < n; i++)index.put(t.charAt(i), i);for(char ch : croakOfFrogs){if(ch == t.charAt(0)){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{int i = index.get(ch);if(hash[i - 1] == 0) return -1;hash[i - 1]--; hash[i]++;}}for(int i = 0; i < n - 1; i++)if(hash[i] != 0)return -1;return hash[n - 1];}
}