(B卷,200分)- 字符匹配（Java & JS & Python）

题目描述

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

‘.’ 匹配任意单个字符，’*’ 匹配零个或多个任意字符；

判断字符串是否匹配，是要涵盖整个字符串的，而不是部分字符串。

输入描述

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

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

不需要考虑异常场景。

输出描述

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

用例

题目解析

本题的最佳题解策略是动态规划，即基于动态规实现模拟正则匹配。

具体解析请看我写的这篇博客：

2023.08.15

本题收集题目时，题目描述是错的…….，现在已改正。

新的题目描述中中关于 "*" 的描述，和正则的 "*" 量词符是不等价的。

’*’ 匹配零个或多个任意字符，因此题目中的"*" 应该和 正则表达式 ".*" 等价。

本题正则解法可以100%通过。

正则解法

JavaScript算法源码

/* 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) {
  reg = reg.replaceAll("*", "(.*)");

  const regExp = new RegExp(`^${reg}$`);

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

  if (ans.length == 0) return "-1";
  else return ans.join(",");
}

Java算法源码

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

public class Main {
  // 输入获取
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] arr = sc.nextLine().split(" ");
    String reg = sc.nextLine();

    System.out.println(getResult(arr, reg));
  }

  // 算法入口
  public static String getResult(String[] arr, String reg) {
    reg = reg.replaceAll("\*", "(.*)");

    Pattern compile = Pattern.compile("^" + reg + "$");

    StringJoiner sj = new StringJoiner(",");
    for (int i = 0; i < arr.length; i++) {
      if (compile.matcher(arr[i]).matches()) {
        sj.add(i + "");
      }
    }

    if (sj.length() == 0) return "-1";
    else return sj.toString();
  }
}

Python算法源码

import re

# 输入获取
arr = input().split()
reg = input().replace("*", "(.*)")


# 算法入口
def getResult():
    c = re.compile(f"^{reg}$")

    ans = []
    for i in range(len(arr)):
        if c.match(arr[i]):
            ans.append(i)

    if len(ans) == 0:
        return "-1"
    else:
        return ",".join(map(str, ans))


# 算法调用
print(getResult())

动态规划解法

Java算法源码

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  // 输入获取
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] arr = sc.nextLine().split(" ");
    String reg = sc.nextLine();

    System.out.println(getResult(arr, reg));
  }

  // 算法入口
  public static String getResult(String[] arr, String reg) {
    reg = reg.replaceAll("\*", ".*");

    StringJoiner sj = new StringJoiner(",");

    for (int i = 0; i < arr.length; i++) {
      if (isMatch(arr[i], reg)) sj.add(i + "");
    }

    if (sj.length() == 0) return "-1";
    else return sj.toString();
  }

  public static boolean isMatch(String s, String p) {
    s = " " + s;
    p = " " + p;

    int n = s.length();
    int m = p.length();

    boolean[][] dp = new boolean[n][m];
    dp[0][0] = true;

    for (int i = 0; i < n; i++) {
      // 内层循环遍历的是正则p的范围，如果j=0.那么代表正则为空，此时匹配结果必然为false，而dp数组初始化时所有元素都初始化为了false，因此这里j可以从1开始
      for (int j = 1; j < m; j++) {
        if (p.charAt(j) == '*') {
          dp[i][j] =
              (j >= 2 && dp[i][j - 2])
                  || (eq(p.charAt(j - 1), s.charAt(i)) && i >= 1 && dp[i - 1][j]);
        } else {
          dp[i][j] = eq(p.charAt(j), s.charAt(i)) && i >= 1 && dp[i - 1][j - 1];
        }
      }
    }

    return dp[n - 1][m - 1];
  }

  public static boolean eq(char p, char s) {
    return p == s || p == '.';
  }
}

JavaScript算法源码

/* 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) {
  reg = reg.replaceAll("*", ".*");

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

  if (ans.length == 0) return -1;
  else return ans.join(",");
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  s = " " + s;
  p = " " + p;

  const n = s.length;
  const m = p.length;

  const dp = new Array(n).fill(0).map(() => new Array(m).fill(false));
  dp[0][0] = true;

  for (let i = 0; i < n; i++) {
    // 内层循环遍历的是正则p的范围，如果j=0.那么代表正则为空，此时匹配结果必然为false，而dp数组初始化时所有元素都初始化为了false，因此这里j可以从1开始
    for (let j = 1; j < m; j++) {
      if (p[j] == "*") {
        dp[i][j] =
          (j >= 2 && dp[i][j - 2]) ||
          (eq(p[j - 1], s[i]) && i >= 1 && dp[i - 1][j]);
      } else {
        dp[i][j] = eq(p[j], s[i]) && i >= 1 && dp[i - 1][j - 1];
      }
    }
  }

  return dp[n - 1][m - 1];
};

function eq(p, s) {
  return p == s || p == ".";
}

Python算法源码

# 输入获取
arr = input().split()
reg = input().replace("*", ".*")


def eq(p, s):
    return p == s or p == '.'


def isMatch(s, p):
    s = " " + s
    p = " " + p

    n = len(s)
    m = len(p)

    dp = [[False] * m for _ in range(n)]
    dp[0][0] = True

    for i in range(n):
        # 内层循环遍历的是正则p的范围，如果j=0.那么代表正则为空，此时匹配结果必然为false，而dp数组初始化时所有元素都初始化为了false，因此这里j可以从1开始
        for j in range(1, m):
            if p[j] == '*':
                dp[i][j] = (j >= 2 and dp[i][j - 2]) or (eq(p[j - 1], s[i]) and i >= 1 and dp[i - 1][j])
            else:
                dp[i][j] = eq(p[j], s[i]) and i >= 1 and dp[i - 1][j - 1]

    return dp[n - 1][m - 1]


# 算法入口
def getResult():
    ans = []
    for i in range(len(arr)):
        if isMatch(arr[i], reg):
            ans.append(i)

    if len(ans) == 0:
        return "-1"
    else:
        return ",".join(map(str, ans))


# 算法调用
print(getResult())