本文共 4037 字，大约阅读时间需要 13 分钟。

题目描述

Given an input string (s) and a pattern §, implement regular expression matching with support for ‘.’ and ‘*’.

给定一个字符串s和匹配的模板p，使用“.”和“*”，实施正则表达式的匹配

‘.’ Matches any single character.

‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

“.”匹配单个字母

“*”匹配零个或者多个该字符之前的元素。 这种匹配应该包括整个输入的字符串，而不是局部

Note:

• s could be empty and contains only lowercase letters a-z.
• s可以是空的字符串，或者仅仅包含小写的字符串
• p could be empty and contains only lowercase letters a-z, and characters like . or *.
• p可以是空的，或者仅仅包含所有的小写字母和“*”和“.”的字符
  Example 1:

Input:

s = “aa” p = “a” Output: false Explanation: “a” does not match the entire string “aa”. Example 2:

Input:

s = “aa” p = “a*” Output: true Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”. *表示有零个或者多个元素a，因此，通过一次重复，变成了aa Example 3:

Input:

s = “ab” p = “."

Output: true

Explanation: ".” means “zero or more (*) of any character (.)”. Example 4:

Input:

s = “aab” p = “cab” Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”. Example 5:

Input:

s = “mississippi” p = “misisp*.” Output: false

思路分析

• 方法一：按照正向，从左往右进行分析
  • 仿照两个栈进行操作：
    • P栈：
      • 向下看两个元素，如果栈顶的下一个元素是"*"，表示" * "前的元素由0，或多个的情况，有以下几种处理方式
        • 表示零次出现，那么S栈不发生改变，P栈连续弹出两个元素
        • 表示一次或者多次出现，那么S栈连续弹出，直到和P栈栈顶的元素不同为止。
    • 处理"."，和匹配字符的情况一同处理。
    • 每一次弹出都要判定，是否当前弹出的元素已经是最后一个元素

总结：如果按照正向从左往右进行分析，会出现很多的分支情况，而且会有很多的特例。

• 方法二：按照逆向从右往左，从后往前进行分析：
  • ” * “号前肯定有一个字符，其也只影响这一个字符
  • 将问题转换为：最右端的字符串是否匹配 + 剩余字串是否匹配的问题。
    • 将问题有一个大问题化成两个小问题，而剩余子串是否匹配和打字穿是否匹配是规模不一样的同一问题
  • 用一个二维数组来表示剩余字串是否匹配
    • s（0,i - 1） ： 表示下标从0到i的S串
    • p（0,j - 1） : 表示下标从0到j的P串
    • dp[i][j] : 取值为true和false：
      • true表示 s（0,i - 1）和p（0,j - 1）两个字串相互匹配
      • false表示s（0,i - 1）和p（0,j - 1）两个字串不匹配
  • 有以下几种特殊情况
    • s[i - 1]和p[j - 1]匹配：
      • s串被拆为两部分：s（0，i-2）和 s[i - 1]；
      • p串被拆分为两部分：p（0，j - 2）和p[j - 1]；
      • S和P是否匹配 = s（0，i-2）和p（0，j - 2），因为最有两个字符串已经匹配，转化为数组：dp[i][j] = dp[i - 1][j - 1]。（其中dp[i][j]表示s（0，i- 1）的完整S串和p（0，j - 1）的完整的p串是否匹配，dp[i - 1][j - 1]则表示分别去除了最后一个字符的剩余字串是否匹配）
    • s[i - 1]和p[j - 1]不匹配
      • p[j - 1]不是"*"，说明不匹配，dp[i][j] = false;确实不匹配
      • p[j - 1]是"*"，又有两种情况：
        * 情况一：s[i - 1]和p[j - 2]匹配，即"字母 + *"的组合可用于匹配的多个相同的字母。将s中已经和p匹配的字符弹出，变成s[i - 1 - 1]和p[j - 2]是否匹配的问题，转成数组变为dp[i][j] = dp[i - 1][j];
        * 情况二： s[i - 1]和p[j - 2]不匹配，可以字母消失，p将不匹配的组合弹出，在和s剩余的字串进行比较。进而变成s[i - 1]和p[j - 3]，转成数组dp[i][j] = dp[i][j - 2]
• 几个基本的情况
  • p为空串，s不为空串，坑定不匹配
  • s为空串，但是p部位空串，想匹配，p是字母加星号的组合
  • s和p都为空串，那么一定匹配

代码实现——写了半天都不能通过

思路修改——由简入繁

• 假设只有P中只有两种字符：所有的小写的字母和"."
• 逐步添加"*"的功能
  • 如果"*"可以表示0个或者1个字符
  • 如果"*"可以表示0个或者多个字符

代码实现

解答分析

• 鉴于该题有很好的子结构，可以不断简化字符串，从而得出最终的答案。主要思路是构造一个二维的矩阵，具体如下

代码实现

bool isMatch4(char *s,char *p){
       if(!*s || !*p)    {
           return false;    }    //建立对应的二维数组    int plen = strlen(p),slen = strlen(s);    bool dp[slen+1][plen+1];    //将dp[0][0]赋予true，将其余各项默认为false    dp[0][0] = 1;    for(int i =0; i < slen + 1;i ++)    {
           for(int j = 0;j < plen + 1;j ++)        {
               dp[i][j] = false;        }    }    //将第零行先赋值    for(int j = 1;j < plen +1 ;j ++)    {
           if(*(p+j-1) == '*')        {
               dp[0][j] = dp[0][j -2];        }    }    for(int i = 1;i < slen + 1;i ++)    {
           for(int j = 1;j < plen + 1;j ++)        {
               //情况一，S末位的字符和P末位的字符匹配成功            if(*(s + i - 1) == *(p + j - 1) ||  *(p+j-1) == '.')            {
                   dp[i][j] = dp[i - 1][j - 1];            }            else if(*(p + j - 1)=='*')            {
                   //如果*号之前字母和text中的字母相匹配，那么可以直接将a退出对应的匹配中                if(*(p + j - 2) == *(s + i - 1) || *(p + j - 2) == '.')                {
                       dp[i][j] = dp[i - 1][j] | dp[i - 1][j - 2] | dp[i][j - 2];                }                else                {
                       //扫描遇见了空格取决于其之前两个位置的字符，能否成功的匹配                    dp[i][j] = dp[i][j - 2];                }            }        }    }    //输出对应的矩阵，验证一下    printf("\n");    for(int i =0; i < slen + 1;i ++)    {
           for(int j = 0;j < plen + 1;j ++)        {
               printf("%d  ",dp[i][j]);        }        printf("\n");    }    return dp[slen][plen];}

转载地址：http://pggpb.baihongyu.com/