LeetCode 1419 数青蛙：基于模拟的状态机解法

题目链接：

1419. 数青蛙 - LeetCode

问题描述

给定一个字符串 croakOfFrogs，表示若干只青蛙发出的叫声序列。每只青蛙必须按顺序发出 'c', 'r', 'o', 'a', 'k' 五个声音才能完成一次完整的叫声。如果字符串中的字符无法组成合法的叫声序列，则返回 -1；否则返回所需的最少青蛙数量。

解题思路

这本质上是一个状态机模拟问题。我们可以将青蛙的发声过程看作五个状态的流转：

1. c: 开始叫
2. r: 继续
3. o: 继续
4. a: 继续
5. k: 结束

为了计算最少需要多少只青蛙，我们需要维护当前处于每个阶段的青蛙数量。当遇到一个新的字符时，检查是否有青蛙处于前一个阶段：

• 遇到 'c'：优先复用已经发完 'k' 的青蛙（即从 'k' 状态回到 'c' 状态），如果没有可用的，说明需要新青蛙。无论哪种情况，该青蛙现在都处于 'c' 阶段。
• 遇到其他字符：必须存在一只青蛙正处于前驱字符的阶段。例如遇到 'r'，必须有青蛙在 'c' 阶段。如果找不到，说明序列非法，直接返回 -1。

遍历结束后，所有青蛙都应该处于 'k' 阶段（即完成了叫声）。如果还有青蛙停留在中间任何阶段，说明序列不完整，返回 -1。

C++ 代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        
        // 记录字符映射下标关系，方便查找前驱
        unordered_map<char, int> index;
        for (int i = 0; i < n; i++) {
            index[s[i]] = i;
        }
        
        // hash[i] 表示当前处于第 i 个字符阶段的青蛙数量
        vector<int> hash(n);
        
        for (auto& ch : croakOfFrogs) {
            if (ch == 'c') {
                // 尝试复用已完成叫声的青蛙（hash[n-1]）
                if (hash[n - 1] != 0) {
                    hash[n - 1]--;
                }
                // 进入 c 阶段
                hash[0]++;
            } else {
                int t = index[ch];
                // 检查前驱阶段是否有青蛙
                if (hash[t - 1] == 0) {
                    return -1;
                }
                // 从前驱阶段移动到当前阶段
                hash[t - 1]--;
                hash[t]++;
            }
        }
        
        // 检查是否所有青蛙都完成了叫声（都在 k 阶段）
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) {
                return -1;
            }
        }
        
        return hash[n - 1];
    }
};

关键点总结

• 状态复用：这是贪心策略的核心。一旦青蛙完成 'k'，它就可以立即开始新的 'c'，不需要额外增加计数。
• 合法性校验：每一步转移都必须有源状态支持，否则直接判定无效。
• 最终检查：循环结束后，除了 'k' 阶段外，其他阶段计数必须为 0，否则意味着有青蛙没叫完就中断了。