Medium

题目描述

给你字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声 “croak” 的组合。由于多只青蛙可以同时蛙鸣，所以多个 “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 <= 10^5
  • 字符串中的字符只有 ‘c’, ‘r’, ‘o’, ‘a’ 或者 ‘k’

解题思路

这道题需要模拟青蛙发出"croak"声音的过程。关键思路是状态机和贪心策略：

核心思想：

  1. 每只青蛙必须按照固定顺序 ‘c’ → ‘r’ → ‘o’ → ‘a’ → ‘k’ 发出声音
  2. 我们需要追踪处于不同状态的青蛙数量：刚发出’c’的、发出’cr’的、发出’cro’的、发出’croa’的
  3. 当遇到字符时，贪心地将其分配给已有的青蛙，如果没有合适的青蛙则创建新青蛙

算法步骤：

  1. 用四个计数器分别记录处于状态’c’、‘cr’、‘cro’、‘croa’的青蛙数量
  2. 遍历字符串，根据当前字符更新状态：
    • ‘c’：新青蛙开始叫声，c_count++
    • ‘r’：必须有处于’c’状态的青蛙，c_count–，cr_count++
    • ‘o’：必须有处于’cr’状态的青蛙，cr_count–，cro_count++
    • ‘a’：必须有处于’cro’状态的青蛙，cro_count–，croa_count++
    • ‘k’：必须有处于’croa’状态的青蛙，croa_count–（青蛙完成一次叫声）
  3. 如果任何时候对应状态的青蛙数量不足，返回-1
  4. 最后检查是否所有青蛙都完成了叫声（所有计数器都为0）

时间复杂度分析： O(n)，只需遍历一次字符串 空间复杂度分析： O(1)，只使用常数个变量

代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int c = 0, cr = 0, cro = 0, croa = 0;
        int maxFrogs = 0;
        
        for (char ch : croakOfFrogs) {
            if (ch == 'c') {
                c++;
            } else if (ch == 'r') {
                if (c == 0) return -1;
                c--;
                cr++;
            } else if (ch == 'o') {
                if (cr == 0) return -1;
                cr--;
                cro++;
            } else if (ch == 'a') {
                if (cro == 0) return -1;
                cro--;
                croa++;
            } else if (ch == 'k') {
                if (croa == 0) return -1;
                croa--;
            } else {
                return -1;
            }
            
            // 当前活跃的青蛙数量
            int activeFrogs = c + cr + cro + croa;
            maxFrogs = max(maxFrogs, activeFrogs);
        }
        
        // 检查是否所有青蛙都完成了叫声
        if (c == 0 && cr == 0 && cro == 0 && croa == 0) {
            return maxFrogs;
        } else {
            return -1;
        }
    }
};

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c = cr = cro = croa = 0
        max_frogs = 0
        
        for ch in croakOfFrogs:
            if ch == 'c':
                c += 1
            elif ch == 'r':
                if c == 0:
                    return -1
                c -= 1
                cr += 1
            elif ch == 'o':
                if cr == 0:
                    return -1
                cr -= 1
                cro += 1
            elif ch == 'a':
                if cro == 0:
                    return -1
                cro -= 1
                croa += 1
            elif ch == 'k':
                if croa == 0:
                    return -1
                croa -= 1
            else:
                return -1
            
            # 当前活跃的青蛙数量
            active_frogs = c + cr + cro + croa
            max_frogs = max(max_frogs, active_frogs)
        
        # 检查是否所有青蛙都完成了叫声
        if c == 0 and cr == 0 and cro == 0 and croa == 0:
            return max_frogs
        else:
            return -1

public class Solution {
    public int MinNumberOfFrogs(string croakOfFrogs) {
        int c = 0, cr = 0, cro = 0, croa = 0;
        int maxFrogs = 0;
        
        foreach (char ch in croakOfFrogs) {
            if (ch == 'c') {
                c++;
            } else if (ch == 'r') {
                if (c == 0) return -1;
                c--;
                cr++;
            } else if (ch == 'o') {
                if (cr == 0) return -1;
                cr--;
                cro++;
            } else if (ch == 'a') {
                if (cro == 0) return -1;
                cro--;
                croa++;
            } else if (ch == 'k') {
                if (croa == 0) return -1;
                croa--;
            } else {
                return -1;
            }
            
            // 当前活跃的青蛙数量
            int activeFrogs = c + cr + cro + croa;
            maxFrogs = Math.Max(maxFrogs, activeFrogs);
        }
        
        // 检查是否所有青蛙都完成了叫声
        if (c == 0 && cr == 0 && cro == 0 && croa == 0) {
            return maxFrogs;
        } else {
            return -1;
        }
    }
}

var minNumberOfFrogs = function(croakOfFrogs) {
    let c = 0, r = 0, o = 0, a = 0;
    let frogs = 0;
    let maxFrogs = 0;
    
    for (let char of croakOfFrogs) {
        if (char === 'c') {
            c++;
            frogs++;
            maxFrogs = Math.max(maxFrogs, frogs);
        } else if (char === 'r') {
            if (c === 0) return -1;
            c--;
            r++;
        } else if (char === 'o') {
            if (r === 0) return -1;
            r--;
            o++;
        } else if (char === 'a') {
            if (o === 0) return -1;
            o--;
            a++;
        } else if (char === 'k') {
            if (a === 0) return -1;
            a--;
            frogs--;
        } else {
            return -1;
        }
    }
    
    return (c === 0 && r === 0 && o === 0 && a === 0) ? maxFrogs : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)，其中 n 是字符串长度，需要遍历字符串一次
空间复杂度O(1)，只使用常数个变量来记录不同状态的青蛙数量

相关题目