1419.Minimum Number of Frogs Croaking¶

1419.Minimum Number of Frogs Croaking¶

Tags: Medium String

Links: https://leetcode.com/problems/minimum-number-of-frogs-croaking/

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 l

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: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

Constraints:

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

class Solution {
    unordered_map<char, int> um;
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        um['c'] = 0; um['r'] = 1; um['o'] = 2; um['a'] = 3; um['k'] = 4;
        unordered_map<int, stack<string>> hashTable;
        int n = croakOfFrogs.size();

        for (int i = 0; i < n; ++i) {
            if (croakOfFrogs[i] == 'c') {
                if (hashTable[4].empty()) hashTable[0].push("c");
                else {
                    hashTable[4].top().push_back('c');
                    hashTable[0].push(hashTable[4].top());
                    hashTable[4].pop();
                }
            }
            else {
                char ch = croakOfFrogs[i];
                int k = um[ch] - 1;
                if (hashTable[k].empty()) return -1;
                else {
                    hashTable[k].top().push_back(ch);
                    hashTable[um[ch]].push(hashTable[k].top());
                    hashTable[k].pop();
                }
            }
        }

        for (int i = 0; i < 4; ++i) if (hashTable[i].size() != 0) return -1;

        return hashTable[4].size();
    }
};

这道题目最初的思路是利用递归去解决，比如题目里的样例：crcoakroak

利用一个字符串变量s保存合法的结果，tmp保存剩余的部分，运行规则就是：

crcoakroak
cr 放入 s
c 放入 tmp
oak 放入 s
roak 放入 tmp
最后s = croak, tmp = croak
首先检验s的长度是否是5的倍数，然后递归去处理tmp

这种思路符合人为处理的思路，但是考虑特殊情况，比如ccccrrrrooooaaaakkkk，每一次处理都需要把整个字符串遍历一次，数据范围是 $10^5$ ，不出意外会超时。所以考虑对其进行优化。

发现字符串的拼接规则其实之和对应字母的前一个字母有关，比如我处理到字符r，那么就应该把它拼接到任何一个以c结尾的字符串后面（如果这个字符串存在的话，不存在直接返回-1），那么如何描述这种前后拼接的关系？于是想到可以利用哈希表来将字符和数字进行映射，所以用um来建立这种映射关系。

接着建立一个哈希表，键是以字符串结尾的字符对应的数字：

0 对应以c结尾的字符串
1 对应以r结尾的字符串
2 对应以o结尾的字符串
3 对应以c结尾的字符串
4 对应以k结尾的字符串

哈希表的值利用一个栈来存储以对应字符结尾的字符串。然后对题目中的样例来处理，展示算法的运行逻辑。

比如crcoakroak：

处理'c'，发现0对应的栈为空，直接推入

处理'r'，应该接到以'c'结尾的字符串后面，于是把最初的'c'后面拼接'r'，然后放入到键为1的栈内

处理'c'，发现0对应的栈为空，直接推入

处理'o'，应该接到以'r'结尾的字符串，于是取出1对应的栈内的字符串，放入2对应的栈内
.....

最后需要先检验序号为0，1，2，3内的栈是否为空，不为空意味着还是存在有的字符串没有拼接，于是返回-1；如果都为空，那么就只需返回栈4内字符串的数量即可。

看了大佬wzc1995的解答，发现其实还可以进一步优化程序，并不需要真正的完成字符串的拼接，完全可以用一个计数器来进行模拟。

优化后的程序：

class Solution {
    unordered_map<char, int> um;
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        um['c'] = 0; um['r'] = 1; um['o'] = 2; um['a'] = 3; um['k'] = 4;
        unordered_map<int, int> hashTable;
        int n = croakOfFrogs.size();

        for (int i = 0; i < n; ++i) {
            if (croakOfFrogs[i] == 'c') {
                if (hashTable[4] == 0) ++hashTable[0];
                else {
                    ++hashTable[0];
                    --hashTable[4];
                }
            }
            else {
                char ch = croakOfFrogs[i];
                int k = um[ch] - 1;
                if (hashTable[k] == 0) return -1;
                else {
                    ++hashTable[um[ch]];
                    --hashTable[k];
                }
            }
        }

        for (int i = 0; i < 4; ++i) if (hashTable[i] != 0) return -1;

        return hashTable[4];
    }
};