檢查給定字串中是否存在給定模式，包括萬用字元 * 和 .。

---

檢查給定字串中是否存在給定模式（包括萬用字元 * 和 .）是計算機科學和程式設計中的一個常見問題。在這個問題中，我們得到一個字串（文字）和一個模式，它可能包含萬用字元字元 '*' 和 '.'，我們需要檢查模式是否與文字匹配。這個問題在許多應用中都會遇到，例如搜尋引擎、檔案系統和網路協議。

在本教程中，我們將討論使用C++解決此問題的一個簡單有效的解決方案。我們將首先解釋問題陳述及其約束條件，然後逐步指導您解決問題。我們還將提供一個實現我們解決方案的C++程式碼示例，並討論其時間和空間複雜度。讓我們開始吧！

問題陳述

目標是確定給定的包含萬用字元字元 '*' 和 '•' 的模式是否與給定的文字字串匹配。模式和文字的長度分別為M和N。如果模式與文字匹配，則輸出“Yes”。否則，輸出“No”。

需要注意的是，'*' 字元匹配其前面字元的零個或多個出現，而 '•' 字元匹配任何單個字元。

示例1

輸入

Text: "hello world"; Pattern: "h*llo w•rld"

輸出

Yes

解釋：在這個例子中，文字是“hello world”，模式是“hllo w•rld”。模式中的''字元匹配其前面字元的零個或多個出現。因此，它匹配文字中的'h'。'•'字元匹配任何單個字元，因此它匹配文字中的空格字元。模式也匹配文字中的'o'和'w'字元。因此，模式與文字匹配，輸出為“Yes”。

示例2

輸入

Text: "cat"; Pattern: "c*t•"

輸出

No

解釋：在這個例子中，文字是“cat”，模式是“ct•”。模式中的''字元匹配其前面字元的零個或多個出現。因此，它匹配文字中的'c'。'•'字元匹配任何單個字元，因此它匹配文字中的'a'字元。但是，模式與文字中的最終't'字元不匹配，因為沒有'•'字元與之匹配。因此，模式與文字不匹配，輸出為“No”。

演算法

1. 初始化一個維度為(n+1) x (m+1)的矩陣dp，其中dp[i][j]表示文字到索引i的子串是否與模式到索引j的子串匹配。

2. 將dp[0][0]設定為true，因為空文字和空模式總是匹配。

3. 迭代模式中從索引1到m的每個字元

• 如果當前字元是''，則將dp[0][i]設定為dp[0][i-1]，表示''可以匹配空子串。

4. 迭代文字中從索引1到n的每個字元

• 對於模式中從索引1到m的每個字元

• 如果文字和模式中當前位置的字元相同，或者模式字元是'?'，則將dp[i][j]設定為dp[i-1][j-1]，因為當前字元匹配。

• 如果模式字元是''，則將dp[i][j]設定為dp[i][j-1]（表示''匹配空子串）或dp[i-1][j]（表示'*'匹配當前文字字元）。

• 否則，將dp[i][j]設定為false。

5. 最終結果儲存在dp[n][m]中，它表示整個文字是否與整個模式匹配。

該演算法使用動態規劃方法構建矩陣，考慮模式中每個字元的三種可能情況：匹配文字中的字元、匹配'?'或匹配'*'。如果整個文字與整個模式匹配，則演算法返回true，否則返回false。

示例

使用C++實現上述演算法

下面的C++程式旨在確定給定的文字是否與包含用'*'和'?'符號表示的萬用字元的模式匹配。該演算法利用動態規劃來構建一個矩陣dp[n+1][m+1]，其中n是文字的長度，m是模式的長度。

輸入

"hello world"; string pattern = "h*llo w?rld";

輸出

Yes

示例

#include <iostream>
#include <vector>
bool isMatch(const std::string& text, const std::string& pattern) {
   int n = text.length();
   int m = pattern.length();
   std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
   dp[0][0] = true;
   for (int i = 1; i <= m; i++) {
      if (pattern[i - 1] == '*') {
         dp[0][i] = dp[0][i - 1];
      }
   }
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
            dp[i][j] = dp[i - 1][j - 1];
         } else if (pattern[j - 1] == '*') {
            dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
         } else {
            dp[i][j] = false;
         }
      }
   }
   return dp[n][m];
}
int main() {
   std::string text = "hello world";
   std::string pattern = "h*llo w?rld";
   if (isMatch(text, pattern)) {
      std::cout << "Yes\n";
   } else {
      std::cout << "No\n";
   }
   return 0;
}

輸出

Yes

結論

總而言之，提供的程式使用動態規劃實現了模式匹配演算法。它確定給定的文字是否與包含萬用字元'*'和'?'符號的模式匹配。透過構建矩陣並迭代地比較字元，該演算法有效地評估匹配條件。這種獨特的方法確保了精確的模式匹配結果，允許進行多功能的文字比較。該程式可作為各種應用程式的有價值工具，例如字串匹配、文字處理和資料分析。其效率和可靠性使其成為處理模式匹配任務時的可靠選擇。