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

剑指offer19. 正则表达式匹配 P124

题目：请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。

这道题和第leetcode44题通配 不同在于: 44题 * 可以是任意字符串 是独立的, 本题 * 作用在前一个字符身上

---

方法1.C++版递归

因为 * 的存在让整个题目复杂，那我们把下一个字符是不是 * 作为划分依据。

Case 1. 当模式中的第二个字符不是“*”时：

1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。 Case 2 . 当模式中的第二个字符是“*”时： 可以有3种匹配方式：

1、模式后移2字符，相当于x*被忽略；比如 str : ab , pattern : b*ab

2、字符串后移1字符，模式后移2字符，x*相当于只匹配一个字符；ab 和 a*b 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；aab 和a*b

bool isMatch(string s, string p) {
           if (p.empty()){
               return s.empty();        }        const char* str = s.c_str(), *pat = p.c_str();         return isMatchCore(str, pat);    }    bool isMatchCore(const char *s, const char *p) {
           if ((*p) == '\0') {
               return *s == '\0';        }        if (*(p + 1) == '*') {
               if (*p == *s || (*p == '.' && *s != '\0')) {
                   return isMatchCore(s + 1, p) 					|| isMatchCore(s + 1, p + 2) 					|| isMatchCore(s, p + 2);            } else {
                   return isMatchCore(s, p + 2);            }        } else if (*p == *s || (*p == '.' && *s != '\0')){
               return isMatchCore(s + 1, p + 1);        } else {
               return false;        }    }

方法2. Java版动态规划

方法类似于44题 但是转移方程不同

note1：

* 跟着他前一个字符走，前一个能匹配上 s[i-1]，* 才能有用，前一个都不能匹配上 s[i-1]，* 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符: dp[i][j] = dp[i][j - 2]; 如： s:ab p:ac*b i=2 j=3 把c*当作整体忽略了

note2:

* 前一个字符可以匹配上s[i-1] dp[i][j] = dp[i-1][j] // 多个字符匹配的情况 or dp[i][j-1] // 单个字符匹配的情况 or dp[i][j-2] // 没有匹配的情况

public boolean isMatch(String s, String p) {
          // s = "a"; p = "*";        s = "$" + s;    // s和p前面加冗余字符的作用 见下面解释        p = "$" + p;        int lens = s.length(), lenp = p.length();        boolean[][] dp = new boolean[lens+1][lenp+1];        dp[0][0] = true;            for (int i = 1; i <= lens; ++i) {
               char cs = s.charAt(i - 1);            for (int j = 1; j <= lenp; ++j) {
                   char cp = p.charAt(j - 1);                                if (cs == cp || cp == '.') // 直接匹配上                    dp[i][j] = dp[i - 1][j - 1];                else if (cp == '*')  {
    // 没有直接匹配上 而且遇到 *					                     if (cs != p.charAt(j - 2) && p.charAt(j - 2) != '.') // note1                        dp[i][j] = dp[i][j - 2]; // 匹配0个(空串)                    else       // note2                        dp[i][j] =  dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];                }                              }        }        return dp[lens][lenp];    }

s = "$" + s;    p = "$" + p;

s和p前面加冗余字符 $ 的作用 主要有两个:

1. 不用像44题前面那样初始化dp[0][j] 也就是当s是空串时，和p的前j的字符匹配情况，因为s非空
2. 在遇到*时else if (cp == ‘*’)后面: 会取到j-2的索引值 索引j从1开始，如果s和p的第一个字符天然匹配之后，就不会执行else if 后面的内容， 也就取不到j-2了。下一次进入循环j=2 j-2开始有效了。

注意的是：前面加的冗余字符不能是s和p里出现的字符

比如加上a: 如果s: a, p: * 会判错。

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