洛谷：P1321：单词覆盖还原

题目

P1321：单词覆盖还原

分析

这道题的关键，是想清楚如何判定原来的单词是boy还是girl。我们以判定boy为例。

仔细分析题意，我们可以得出这样的结论，在最终的字符串s中，

• 如果出现boy，显然boy_count（单词boy的出现次数）需要加1。
• 如果出现bo或者oy，显然boy_count（单词boy的出现次数）需要加1。
• 如果出现b|o|y中的任何一个字符，显然boy_count（单词boy的出现次数）需要加1。

这就是本题的核心算法。girl是否出现也是类似的判定，不过需要更多的分支判定。

另外，按照匹配的强度（匹配boy > bo|oy > b|o|y）顺序，一旦发现更强的匹配，就需要将这些字符“清除”，也就是设置为一个不会在boy/girl出现的字符，程序中是将这些字符设置为'.'），否则在后续匹配更弱的字符串时，就会重新计算。比如：

// 检查三字母组合
if (i + 2 < s.length() && s[i] == 'b' && s[i + 1] == 'o' &&
    s[i + 2] == 'y')
{
    boy_count++;
    s[i] = s[i + 1] = s[i + 2] = '.';
    continue;
}

答案

思考

本题用贪心匹配（强匹配优先）+ 标记清除避免重复计数，适用于字符串覆盖还原场景。时间\(O(n)\)，空间\(O(n)\)。