題目描述

給你一個字符串數組（每個字符串均由小寫字母組成）和一個字符規律（由小寫字母和 . 和 * 組成），識別數組中哪些字符串可以匹配到字符規律上。

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

所謂匹配，是要涵蓋整個字符串的，而不是部分字符串。

輸入描述

第一行為空格分隔的多個字符串，單個字符串長度從 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 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)))