动态规划

最重要的是找到状态和状态转移方式

例子

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a"
输出: true
解释: '' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

输入:
s = "ab"
p = "."
输出: true
解释: "." 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "cab"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "misisp*."
输出: false

题目分析

这里采用动态规划，动态规划最重要的是找到问题的状态，以及如何通过状态转移方式转移到下一个状态。

应该很容易想到定义d[i][j] 来表示字符串长度为i是否匹配pattern长度为j的状态。
然后问题就变成了当我们知道了d[i-1][j-1]的时候，如何获得d[i][j]的状态，比如
d[i][j] 是否为true，如何通过前面的状态来通过数学表达式表示出来。

这里采用自低向上的方法来推导，观察一个例子 string： abc pattern： a*bc

1，首先建立二维数组 d[string.length() + 1][pattern.length() + 1]

2, 初始化二维数组d，
当pattern为空，有0个匹配字符的时候，可以很容易得到下列数组

当string为空，有0个匹配字符的时候，可以很容易得到下列数组

因为当string为空的时候，这里的pattern是a*bc，
a. 当取pattern的1个时候，pattern就是a，所以对应上面表格的d[0][1] = false
b. 当取pattern的2个时候，pattern就是a*，所以对应上面表格的d[0][2] = true
c. 当取pattern的3个时候，pattern就是a*b，所以对应上面表格的d[0][3] = false
d. 当取pattern的4个时候，pattern就是a*bc，所以对应上面表格的d[0][4] = false

现在基本的低已经都有了，然后就是分析如何通过这些基本的状态低，来获取更高的状态。
比如d[1][1]如何通过这些基本的低来表示
先看例子 string当取1个字符的时候，string 是a，
a. 当取pattern的1个时候，pattern就是a，很明显d[1][1] = true
b. 当取pattern的2个时候，pattern就是a*, d[1][1] = true
c. 当取pattern的3个时候，pattern就是a*b，d[1][3] = false
d. 当取pattern的4个时候，pattern就是a*bc，d[1][4] = false

如下表格

同理计算出当string字符取2个时候的表格

可以看到当计算d[i][j]的时候，
当patter[j -1] == '*'的时候，
a: 匹配了0个字符的时候，d[i][j] = d[i][j-2] 比如 b 和 ba*匹配的时候
b：匹配了1个字符的时候， d[i][j] = d[i][j-1] 比如b 和b*匹配的时候
c: *匹配了多个字符的时候, d[i][j] = d[i-1][j] 且(s[i-1] === p[j-2] || p[j-2] === '.')

当patter[j -1] 不等于 '*'的时候
a：d[i][j] = d[i-1][j-1] 且 s[i-1] === p[j-1] || p[j-1] === '.'

所以状态转移方程就找到了

bool isMatch(char* s, char* p) {
    int length_str = (int) strlen(s);
    int length_pattern = (int) strlen(p);

    bool dp[length_str + 1][length_pattern + 1];
    // 初始化边界条件，也就是第0列，第1行
    int i;
    dp[0][0] = true;
    for (i = 1; i < length_str + 1; i++) {
        dp[i][0] = false;
    }

    for (i = 1; i < length_pattern + 1; i++) {
        // 奇数个是不能匹配到0个字符的，因此为假
        if (i % 2) {
            dp[0][i] = false;
        }
            // 当为偶数个的时候，判断隔着一个字符的那个位置，能不能匹配到，如果能，就能
        else if (p[i - 1] == '*') {
            dp[0][i] = dp[0][i - 2];
        } else {
            dp[0][i] = false;
        }
    }

    // 接下来填充数组
    for (i = 1; i < length_str + 1; i++) {
        for (int j = 1; j < length_pattern + 1; ++j) {
            if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
    }


    for (i = 0; i < length_str + 1; i++) {
        for (int j = 0; j < length_pattern + 1; ++j) {
            printf("%s\t", dp[i][j] ? "true" : "false");
        }
        printf("\n");
    }

    return dp[length_str][length_pattern];
}

参考

https://github.com/zhishengqianjun123/leetcode/blob/master/LeetCode/LeetCode:%2010.%20%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D.md#leetcode-10-%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D