LeetCode特定字符序列计数

本文旨在解决一个特定的问题：给定一个仅由字符‘5’、‘2’和‘0’组成的字符串，计算其中不同位置的‘520’子序列的数量。

例如，对于字符串“552200”，存在8个不同的‘520’子序列。

问题分析

解决这一问题的关键在于利用动态规划的思想。我们定义三个变量：sum5、sum2和sum0，分别用于记录以‘5’、‘2’和‘0’结尾的有效子序列的数量。

• 当遇到字符‘5’时，它可以直接作为新子序列的开始，因此sum5增加1。
• 当遇到字符‘2’时，它可以与之前所有以‘5’结尾的子序列组合形成新的‘52’子序列，因此sum2更新为sum2 + sum5。
• 当遇到字符‘0’时，它可以与之前所有以‘2’结尾的子序列组合形成新的‘520’子序列，因此sum0更新为sum0 + sum2。

最终，sum0将包含所有可能的‘520’子序列的数量。

代码实现

int findOccurrences(string S) { int sum5 = 0, sum2 = 0, sum0 = 0; for (char c : S) { switch (c) { case '5': sum5++; break; case '2': sum2 += sum5; break; case '0': sum0 += sum2; break; } } return sum0; }

扩展问题

如果字符串中还包含通配符‘?’，它可以代表‘5’、‘2’或‘0’中的任何一个。在这种情况下，我们需要调整算法，确保每个‘?’都被正确处理。

具体来说，当遇到‘?’时，我们应该按如下顺序处理：

1. 首先考虑‘?’作为‘0’，更新sum0。
2. 然后考虑‘?’作为‘2’，更新sum2。
3. 最后考虑‘?’作为‘5’，更新sum5。

这种顺序确保了每个‘?’只被当作一个字符处理，避免了重复计算。

int findOccurrencesWithWildcard(string S) { int sum5 = 0, sum2 = 0, sum0 = 0; for (char c : S) { switch (c) { case '5': sum5++; break; case '2': sum2 += sum5; break; case '0': sum0 += sum2; break; case '?': sum0 += sum2; sum2 += sum5; sum5++; break; } } return sum0; }