正则表达式匹配：最直观的想法是，递归，由于*比较特殊，其表示前面的字符重复0次、1次、多次，故需要分情况讨论。首先判断pattern是否为空，如果其为空，str也为空，那么可以匹配，反之如果str不为空，那么不可以匹配；接着我们使用first来表示pattern和str的第一位是否匹配，由于前面pattern为空时会返回，故到这里pattern肯定不为空，此时pattern和str第一位匹配的条件是str不为空，并且pattern[0]等于str[0]或者pattern[0]等于'.'；然后我们根据'*'来分情况讨论，由于'*'不能单独使用，其前面至少要有一个字符，所以每次都是判断pattern[1]，如果pattern[1]等于'*'，那么有两种情况，一是'*'重复0次，那么就是比较str和以pattern[2]开头的字符串是否匹配，二是'*'重复1次或者多次，两者都是以first为前提再比较以str[1]开头的字符串和pattern是否匹配，反之如果pattern[1]不等于'*'，那么以first为前提再比较以str[1]开头的字符串和pattern[1]是否匹配。

bool match(string str, string pattern) 
{
    //base1：p空 s空 匹配
    //base2：p空 s不空 不匹配
    if(pattern.empty()) 
       return str.empty();
    //判断p和s的第一位是否匹配，其中走到这里说明p肯定不为空，故此处需要显示要求s也不为空
    bool first=(!str.empty())&&(str[0]==pattern[0]||pattern[0]=='.');
    //如果p的第二个为*，则分为重复0次和重复多次，重复0次即s和p[2]开始的字符串匹配与否，重复多次就是建立在p和s的第一位匹配上且s[1]和p开始的字符串匹配与否
    if(pattern.length()>=2&&pattern[1]=='*')
       return (first&&match(str.substr(1),pattern))||match(str,pattern.substr(2));
    //否则看p和s第一位匹配的基础上，s[1]和p[1]开始的字符串是否可以匹配上
    else
       return first&&match(str.substr(1),pattern.substr(1));
}

优化：由于涉及到状态转移，那么可以用递归做的也可以用动态规划来做。其中dp[i][j]表示str的前i位与pattern的前j位是否匹配，其对应的是str[i-1]和pattern[j-1]，注意区分元素位置和元素下标。首先进行初始化，注意当str为空串的时候，pattern不为空串也是有可能匹配的，只需要通过*和*前面一位来两位两位的不断删除即可。在正式dp[i][j]赋值时，首先判断pattern当前元素是否为*，如果是则匹配0次或者1次或者多次，0次就是dp[i][j-2]，1次或者多次就是dp[i-1][j]，并且str的当前元素与pattern的当前元素的前一位匹配，相当于又重复了一次，反之如果不是则需要str的前i-1位与pattern的前j-1位匹配并且str的当前元素与pattern的当前元素匹配。最后返回dp[str.size()][pattern.size()]即可。

bool match(string str, string pattern) 
{
   int len1=str.size(),len2=pattern.size();
   vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));  //dp[i][j]表示str的前i位与pattern的前j位是否匹配
   dp[0][0]=true; //两个空字符串肯定匹配
   for(int j=1;j<len2+1;j++) //初始化str为空而pattern不为空的情况，看是否可以使得pattern两位两位的不断删除从而变成空串与str匹配
   {
      //dp对应的下标表示的是从1开始的字符串位数而pattern和str对应的下标是从0开始的字符串元素下标
      //*不能作为第一个元素，其前面要有元素
      if(pattern[j-1]=='*'&&j-1>=1)
      {
          dp[0][j]=dp[0][j-2];
      }
   }
   for(int i=1;i<len1+1;i++)
   {
      for(int j=1;j<len2+1;j++)
      {
         //如果pattern当前元素为*则需要分类讨论，dp[i][j-2]表示*匹配0次，后者dp[i-1][j]是表示str的前i-1位都和pattern的前j位匹配，且str当前元素与pattern当前元素的前一位匹配，其表示匹配1次或者多次
         if(pattern[j-1]=='*')
            dp[i][j]=dp[i][j-2]||(dp[i-1][j]&&(str[i-1]==pattern[j-2]||pattern[j-2]=='.'));
         //否则str的前i-1和pattern的前j-1位匹配并且两者的当前元素也匹配
         else
            dp[i][j]=dp[i-1][j-1]&&(str[i-1]==pattern[j-1]||pattern[j-1]=='.');
       }
   }
   return dp[len1][len2];
}