[leetcode] 1419. Minimum Number of Frogs Croaking

[leetcode] 1419. Minimum Number of Frogs Croaking

Description

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"Output: 1 Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"Output: 2 Explanation: The minimum number of frogs is two. The first frog could yell "crcoakroak".The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"Output: -1Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"Output: -1

Constraints:

1 <= croakOfFrogs.length <= 10^5All characters in the string are: ‘c’, ‘r’, ‘o’, ‘a’ or ‘k’.

分析

题目的意思是：给定一个字符串，问最少由多少个croak字符串组成，其中croak可以分开，这种情况要单独算一种。这道题要找规律，首先统计字符的频率，如果出现了其他字符，则直接返回-1.最后统计出来的频率要相等，否则也要返回-1.如何统计croak的数量呢，用一个cur来统计当前c字符的数量，如果遇见k要减1，维护最小值res就行了，这个要找规律，不然就麻烦，哈哈。

代码

class Solution: def minNumberOfFrogs(self, croakOfFrogs: str) -> int: d=collections.defaultdict(int) cur=0 res=0 for ch in croakOfFrogs: d[ch]+=1 if(ch=='c'): cur+=1 elif(ch=='k'): cur-=1 res=max(res,cur) if(d['c']

参考文献

​​[LeetCode] Py O(n) Sol: Easy to Understand, Ask Doubt​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。