(B卷,100分)- 相对开音节（Java & JS & Python）

题目描述

相对开音节构成的结构为：辅音 + 元音（aeiou）+ 辅音(r除外) + e。

常见的单词有bike、cake等。

给定一个字符串，以空格为分隔符，反转每个单词中的字母，若单词中包含如数字等其他非字母时不进行反转。

反转后计算其中含有相对开音节结构的子串个数（连续的子串中部分字符可以重复）。

输入描述

字符串，以空格分割的多个单词，字符串长度<10000，字母只考虑小写

输出描述

含有相对开音节结构的子串个数，注：个数<10000

用例

题目解析

本题主要是两部分逻辑：

• 反转操作：如果单词中包含非小写字母，则不反转，否则反转
• 反转操作后：每个单词含有多个相对开音节子串

其中，反转操作很简单，遍历一遍单词字符，或者用正则表达式 [^a-z] 去匹配单词，看有没有非小写字母，没有的话，就反转单词。

之后，要求解每个单词中含有多少个相对开音节子串，根据题目对应相对开音节结构定义，这个子串长度固定为4，因此我们可以用滑窗去尺取子串，接下来就是判断子串是否为相对开音节结构，这个最好的方式是基于正则表达式，如下：

[^aeiou][aeiou][^aeiour]e

一旦子串可以被上面正则匹配成功，则是一个符合要求的相对开音节结构。

本题，其实还可以优化逻辑，即将反转单词的动作优化掉。

假设一个单词不包含非小写字母字符，则理论上该单词要被反转，然后用下面正则匹配滑窗子串：

[^aeiou][aeiou][^aeiour]e

但是，如果我们不对单词反转呢？那么是不是意味着，只需要将正则反转后，匹配子串即可？反转正则如下：

e[^aeiour][aeiou][^aeiou]

2023.07.10

对于正则表达式：[^aeiou] 来匹配非元音字母 是有缺陷的，因为该正则实际匹配的是 非元音的所有字符，而不是字母。

但是非元音小写字母的正则写起来实在太繁琐了，因此，我们可以在检测相对开音节之前，对子串做一次是否含有非字母的检查，如果含有非字母，则必然不可能是相对开音节。

Java算法源码

import java.util.Scanner;
import java.util.regex.Pattern;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] words = sc.nextLine().split(" ");
    System.out.println(getResult(words));
  }

  public static int getResult(String[] words) {
    int count = 0;

    Pattern nonLetter = Pattern.compile("[^a-z]");
    Pattern reg1 = Pattern.compile("[^aeiou][aeiou][^aeiour]e");
    Pattern reg2 = Pattern.compile("e[^aeiour][aeiou][^aeiou]");

    for (String word : words) {
      Pattern reg = nonLetter.matcher(word).find() ? reg1 : reg2;

      for (int i = 0; i <= word.length() - 4; i++) {
        String seg = word.substring(i, i + 4);

        if (nonLetter.matcher(seg).find()) continue;

        if (reg.matcher(seg).find()) count++;
      }
    }

    return count;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const words = line.split(" ");
  console.log(getResult(words));
});

function getResult(words) {
  let count = 0;

  const nonLetter = /[^a-z]/;
  const reg1 = /[^aeiou][aeiou][^aeiour]e/;
  const reg2 = /e[^aeiour][aeiou][^aeiou]/;

  words.forEach((word) => {
    const reg = nonLetter.test(word) ? reg1 : reg2;

    for (let i = 0; i <= word.length - 4; i++) {
      const seg = word.substr(i, 4);
      if (nonLetter.test(seg)) continue;
      if (reg.test(seg)) count++;
    }
  });

  return count;
}

Python算法源码

# 输入获取
import re

words = input().split()


# 算法入口
def getResult():
    count = 0

    nonLetter = re.compile(r"[^a-z]")
    reg1 = re.compile(r"[^aeiou][aeiou][^aeiour]e")
    reg2 = re.compile(r"e[^aeiour][aeiou][^aeiou]")

    for word in words:
        reg = reg1 if nonLetter.search(word) else reg2

        for i in range(len(word) - 3):
            seg = word[i:i + 4]

            if nonLetter.search(seg):
                continue

            if reg.match(seg):
                count += 1

    return count


# 算法调用
print(getResult())