华为机试 - 字符串匹配

目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

给你一个字符串数组（每个字符串均由小写字母组成）和一个字符规律（由小写字母和.和*组成），识别数组中哪些字符串可以匹配到字符规律上。

‘.’ 匹配任意单个字符，’*’ 匹配零个或多个前面的那一个元素，所谓匹配，是要涵盖整个字符串的，而不是部分字符串。

输入描述

第一行为空格分割的多个字符串，1<单个字符串长度<100，0，1<字符串个数<100

第二行为字符规律，1<字符串个数<100

第二行为字符规律，1<=字符规律长度<=50

不需要考虑异常场景。

输出描述

匹配的字符串在数组中的下标（从0开始），多个匹配时下标升序并用,分割，若均不匹配输出-1

用例

题目解析

会正则表达式的人机试遇到这题会流泪，不会正则表达式的人遇到这题也会流泪。

不同的是，一个是开心的泪，一个是苦涩的泪。

机试，追求最短时间，最高准确率，当然后面面试的时候，问道这题还是需要回答出动态规划解法的思路。

本题算是10. 正则表达式匹配 - 力扣（LeetCode）

变种题。关于动态规划的解法，大家可以去LeetCode上看看。

算法源码

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

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

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const arr = lines[0].split(" ");
    const reg = lines[1];

    console.log(getResutlt(arr, reg));
    lines.length = 0;
  }
});

function getResutlt(arr, reg) {
  const regExp = new RegExp(`^${reg}$`);

  const ans = [];
  for (let i = 0; i < arr.length; i++) {
    if (regExp.test(arr[i])) ans.push(i);
  }

  return ans.join();
}