P3284. 相对开音节

解题思路

除了滑窗过程以外，本题还涉及到诸多字符串处理的模拟过程，难度不大但是综合性较强，也考察一些基础语法和字符串相关 API 的应用，需要仔细读题并理解题意。

数据预处理

对于输入的整个字符 s，我们首先按照空格进行分割为列表 lst，然后判断 lst 里的元素 lst[i]。 如果该元素仅包含字母，则进行反转，否则不进行处理。代码为

单个相对开音节的判断

假设我们已知一个长度为 4 的字符串 word，它必须满足以下条件，才是一个相对开音节：

• 第一个字符为辅音字母
• 第二个字符为元音字母
• 第三个字符为不是 r 的辅音字母
• 第四个字符为 e

因此我们可以构造一个 check() 函数，来判断长度为 4 的字符串 word 是否为相对开音节。 如果是，则返回 1，表示相对开音节的总计数 +1。

特别注意：关于 word[0] 和 word[2] 的判断，除了判断 word[0] 和 word[2] 不位于 vowel 集合中，还必须判断 word[0] 和 word[2] 是一个字母。否则，形如 ca&e 或者 #ake 这样的字符串会被错判为相对开音节。

对每一个字符串进行滑窗过程

处理完 lst 中的元素之后，我们再次遍历 lst 中的每一个字符串元素 lst[i]。如果：

• lst[i] 的长度小于 4，那么一定无法寻找到相对开音节，可以直接跳过
• lst[i] 的长度大于等于 4，则对 lst[i] 本身进行窗口长度为 4 的滑窗计算，考虑 lst[i] 的每一个长度为 4 的子字符串 word 是否为相对开音节。

故整体代码如下：

复杂度分析 设 L 为输入字符串的总长度（所有单词的长度之和加上分隔空格）。

• 时间复杂度：O(L)。整个流程分三段：按空格切分成单词列表 lst，O(L)；逐个单词用 isalpha 判断是否纯字母并对纯字母单词做反转，这两个操作对每个单词都是线性的，合计 O(L)；滑窗统计阶段，对每个长度不小于 4 的单词枚举它所有长度为 4 的连续子串，长度为 m 的单词有 m-3 个窗口，而每个窗口的切片和 check 判断都只涉及固定的 4 个字符（辅音、元音、非 r 辅音、字母 e 四个条件各查一次），是 O(1)，因此这一段合计也是 O(L)。三段相加，总体是对输入的常数趟线性扫描。
• 空间复杂度：O(L)。主要是切分出的单词列表 lst 以及反转单词时产生的新字符串；每次滑窗取出的 word 只有 4 个字符，是常数开销；元音集合 vowel 固定 5 个元素。

注意本题窗口长度固定为 4，所以「滑窗」实际退化成逐位枚举起点，不需要维护增量状态，这也是每个窗口能 O(1) 判断的原因。