机试题——字符匹配

题目描述

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

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

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

输入描述

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

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

不需要考虑异常场景。

输出描述

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

用例输入

ab aab 
.*

0,1

说明：

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

ab aab 
a.b

1

说明：

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

解题思路

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

1. 基础状态：

   • dp[0][0] = true，表示空字符串和空模式是匹配的。
   • 对于模式中包含 * 的情况，我们需要特别处理。
     • dp[0][j] 表示模式从位置 0 到位置 j 是否可以匹配空字符串。当模式中的字符是 *，它代表前一个字符可以重复零次或者多次。所以，dp[0][j] = dp[0][j-2]。

2. 模式字符匹配：

   • . 匹配任意单个字符：如果模式字符是 .，则可以匹配字符串中的任何字符，因此 dp[i][j] = dp[i-1][j-1]。
   • 字母匹配：如果模式中的字符与字符串中的字符相同，那么我们也需要检查前面部分是否匹配，即 dp[i][j] = dp[i-1][j-1]。

3. 处理 * 字符：

   • * 表示前一个字符可以重复零次或多次。我们需要考虑两种情况：
     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 re

def find_matching_indices(strings, pattern):
    indices = []
    for i, s in enumerate(strings):
        if re.fullmatch(pattern, s):
            indices.append(i)
    return indices

strings = input().split()
pattern = input()
matching_indices = find_matching_indices(strings, pattern)

if not matching_indices:
    print(-1)
else:
    print(",".join(map(str, matching_indices)))