机试题——字符匹配

题目描述

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

. 匹配任意单个字符。
* 匹配零个或多个前面的那一个元素。

所谓匹配，是要涵盖整个字符串的，而不是部分字符串。

输入描述

第一行为空格分隔的多个字符串，单个字符串长度从 1 到 100，字符串个数从 1 到 100。

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

不需要考虑异常场景。

输出描述

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

用例输入

ab aab 
.*

0,1

说明：

"ab" 中 a 匹配 .，b 匹配 * 可以完全匹配。
"aab" 中 a 匹配 .，ab 匹配 * 可以完全匹配。
输出对应字符串数组下标 0,1。

ab aab 
a.b

说明：

"aab" 中第一个 a 匹配 a，第二个 a 匹配 .，b 匹配 b，可以完全匹配。
输出对应字符串数组下标 1。

解题思路

我们使用动态规划来判断字符串是否能够与模式匹配。考虑使用一个二维的 dp 数组来表示匹配情况。dp[i][j] 表示字符串 s 的前 i 个字符是否与模式 p 的前 j 个字符匹配。

基础状态：
- dp[0][0] = true，表示空字符串和空模式是匹配的。
- 对于模式中包含 * 的情况，我们需要特别处理。
  - dp[0][j] 表示模式从位置 0 到位置 j 是否可以匹配空字符串。当模式中的字符是 *，它代表前一个字符可以重复零次或者多次。所以，dp[0][j] = dp[0][j-2]。
模式字符匹配：
- . 匹配任意单个字符：如果模式字符是 .，则可以匹配字符串中的任何字符，因此 dp[i][j] = dp[i-1][j-1]。
- 字母匹配：如果模式中的字符与字符串中的字符相同，那么我们也需要检查前面部分是否匹配，即 dp[i][j] = dp[i-1][j-1]。
处理 * 字符：
- * 表示前一个字符可以重复零次或多次。我们需要考虑两种情况：
  1. * 匹配零次：即前一个字符被去除，检查 dp[i][j-2]。
  2. * 匹配一次或多次：如果当前字符与模式中的字符匹配（或者模式中的字符是 .），那么可以继续检查 dp[i-1][j]。

代码

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;bool check(const string& s, const string& p) {int sl = s.size(), pl = p.size();// dp[i][j] 表示字符串 s 的前 i 个字符是否与模式 p 的前 j 个字符匹配。vector<vector<bool>> dp(sl + 1, vector<bool>(pl + 1, false));dp[0][0] = true;// 需要检查 x* 前面的部分是否能匹配空字符串。for (int j = 1; j <= pl; ++j) {if (p[j - 1] == '*') {dp[0][j] = dp[0][j - 2];}}for (int i = 1; i <= sl; ++i) {for (int j = 1; j <= pl; ++j) {if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];}else if (p[j - 1] == '*') {dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));}}}return dp[sl][pl];
}int main() {// 输入字符串数组vector<string> strings;string input;getline(cin, input);size_t pos = 0;while ((pos = input.find(' ')) != string::npos) {strings.push_back(input.substr(0, pos));input.erase(0, pos + 1);}strings.push_back(input); // 添加最后一个字符串// 输入字符规律string pattern;getline(cin, pattern);// 查找匹配的下标vector<int> res;for (int i = 0; i < strings.size(); i++) {if (check(strings[i], pattern)) {res.push_back(i);}}if (res.empty()) {cout << -1 << endl;}else {for (int i = 0; i < res.size(); ++i) {cout << res[i];if (i < res.size() - 1) {cout << ",";}}cout << endl;}return 0;
}

python

re模块一步出结果

import redef find_matching_indices(strings, pattern):indices = []for i, s in enumerate(strings):if re.fullmatch(pattern, s):indices.append(i)return indicesstrings = input().split()
pattern = input()
matching_indices = find_matching_indices(strings, pattern)if not matching_indices:print(-1)
else:print(",".join(map(str, matching_indices)))