算法题：具有三个符号(*，+，?)的通配符模式匹配

给定文本和通配符模式, 请实现通配符模式匹配算法, 以查找通配符模式是否与文本匹配。匹配项应覆盖整个文本(而非部分文本)。

通配符模式可以包含字符”？”, ” *”和” +”。

‘?’ – matches any single character
‘*’ – Matches any sequence of characters
      (including the empty sequence)
'+' – Matches previous single character
      of pattern

例子：

Input :Text = "baaabaaa", Pattern = "****+ba*****a+", output : true
Pattern = "baaa?ab", output : false 
Pattern = "ba*a?", output : true
Pattern = "+a*ab", output : false 

Input : Text = "aab"
Pattern = "*+"  output : false 
Pattern = "*+b" output : true

情况1：字符为” *”

这里出现两种情况：我们可以忽略” *”字符并移至模式中的下一个字符。 ” *”字符与文本中的一个或多个字符匹配。在这里, 我们将移至字符串中的下一个字符。

情况2：字符是”？”我们可以忽略文本中的当前字符, 而移至图案和文本中的下一个字符。

情况3：字符为” +”

这里出现两种情况：我们将文本的当前字符与模式的前一个字符进行匹配。如果没有先前的字符表示” +”是模式的第一个字符, 那么我们将结果打印为”文本不匹配”。如果前一个字符是” +”, “？”或” *”, 我们将其替换为他们使用的最后一个字符。

情况4：该字符不是通配符

如果文本中的当前字符与样式中的当前字符匹配, 我们将移至样式和文本中的下一个字符。如果它们不匹配, 则通配符模式和文本不匹配。

” *”, “？”的过程类似于通配符模式匹配两个字符:

Here we use a dp table that will contain 
two fields 
Struct DP
{
   // value is true if match possible
   // for current indexes, else false.
   bool value; 

   // Stores the character used 
   // by the symbol that we used 
   // later for symbol '+'
   char ch; 
}

下面的c ++实现了上面的想法。

// C++ program to implement wildcard
// pattern matching algorithm
#include <bits/stdc++.h>
using namespace std;
  
struct DP {
     bool value;
     char ch;
};
  
// Function that matches input str with
// given wildcard pattern
bool strmatch(string str, string pattern, int n, int m)
{
     // empty pattern can only match with
     // empty string
     if (m == 0)
         return (n == 0);
  
     // If first character of pattern is '+'
     if (pattern[0] == '+' )
         return false ;
  
     // lookup table for storing results of
     // subproblems
     struct DP lookup[m + 1][n + 1];
  
     // initialize lookup table to false
     for ( int i = 0; i <= m; i++)
         for ( int j = 0; j <= n; j++) {
             lookup[i][j].value = false ; 
             lookup[i][j].ch = ' ' ; 
         }  
           
     // empty pattern can match with
     // empty string
     lookup[0][0].value = true ;
  
     // Only '*' can match with empty string
     for ( int j = 1; j <= n; j++)
         if (pattern[j - 1] == '*' )
             lookup[j][0].value = 
                    lookup[j - 1][0].value;
  
     // fill the table in bottom-up fashion
     for ( int i = 1; i <= m; i++) {
         for ( int j = 1; j <= n; j++) {
  
             // Two cases if we see a '*'
             // a) We ignore ‘*’ character and move
             // to next character in the pattern, // i.e., ‘*’ indicates an empty sequence.
             // b) '*' character matches with ith
             // character in input
             if (pattern[i - 1] == '*' ) {
                 lookup[i][j].value =
                        lookup[i][j - 1].value || 
                        lookup[i - 1][j].value;
                 lookup[i][j].ch = str[j - 1];
             }
  
             // Current characters are considered as
             // matching in two cases
             // (a) current character of pattern is '?'
             else if (pattern[i - 1] == '?' ) {
                 lookup[i][j].value = 
                           lookup[i - 1][j - 1].value;
                 lookup[i][j].ch = str[j - 1];
             }
  
             // (b) characters actually match
             else if (str[j - 1] == pattern[i - 1])
                 lookup[i][j].value =
                        lookup[i - 1][j - 1].value;
  
             // Current character match
             else if (pattern[i - 1] == '+' )
  
                 // case 1: if previous character is 
                 // not symbol
                 if (pattern[i - 2] != '+' ||
                     pattern[i - 2] != '*' ||
                     pattern[i - 2] != '?' )
                     if (pattern[i - 2] == str[j - 1]) {
                         lookup[i][j].value = 
                            lookup[i - 1][j - 1].value;
                         lookup[i][j].ch = str[j - 1];
                     }
  
                     // case 2 : if previous character 
                     // is symbol (+, *, ? ) then we 
                     // compare current text character 
                     // with the character that is used by
                     // the symbol  at that point. we 
                     // access it by lookup[i-1][j-1]
                     else if (str[j-1] == lookup[i-1][j-1].ch) {
                         lookup[i][j].value =
                               lookup[i - 1][j - 1].value;
                         lookup[i][j].ch =
                               lookup[i - 1][j - 1].ch;
                     }
  
                     // If characters don't match
                     else
                         lookup[i][j].value = false ;
         }
     }
  
     return lookup[m][n].value;
}
  
// Driver code
int main()
{
     string str = "baaabaaa" ;
     string pattern = "*****+ba***+" ;
  
     if (strmatch(str, pattern, str.length(), pattern.length()))
         cout << "Yes" << endl;
     else
         cout << "No" << endl;
  
     return 0;
}

输出如下：

Yes

时间复杂度：O(n * m)