10. Regular Expression Matching

source: https://leetcode.com/problems/regular-expression-matching/

Question

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

思路

这道题里，主要是去判断*的各种情况。

对应到动态规划里的选择：

• 两个字符匹配
  • 存在贪心
    • 可以匹配0次或者任意次，只要有一种情况成立就是valid
  • 不存在贪心
    • 匹配刚好一次
• 两个字符不匹配
  • 存在贪心
    • 匹配0次
  • 不存在贪心
    • invalid

/**
 * 递归+备忘录
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    const cache = {};
    const getCacheData = (i, j) => {
        const key = `${[i, j]}`;
        if (cache[key] === undefined) cache[key] = match(i, j);
        return cache[key];
    };
    const match = (i, j) => {
        // 正则被匹配完，如果字符串也被匹配完，说明匹配
        if (j === p.length) return i === s.length;
        // 字符串被匹配完
        if (i === s.length) {
            // 非x*y*z*的情况
            if ((p.length - j) % 2 === 1) return false;
            for (; j + 1 < p.length; j += 2) if (p[j + 1] !== '*') return false;
            // x*y*z*的情况，说明匹配
            return true;
        }
        // 匹配
        if (s[i] === p[j] || p[j] === '.') {
            // 存在贪心
            // 可以匹配0次或者任意次，只要有一种情况成立就是valid
            if (p[j + 1] === '*') return getCacheData(i, j + 2) || getCacheData(i + 1, j);
            // 不存在贪心
            // 匹配刚好一次
            else return getCacheData(i + 1, j + 1);
        } else {
            // 存在贪心
            // 匹配0次
            if (p[j + 1] === '*') return getCacheData(i, j + 2);
            // 不存在贪心且不匹配
            else return false;
        }
    };
    return match(0, 0);
};

End

对于两个字符串的问题，一定要先找出所有可能性去描述i和j匹配和不匹配时的情况，然后找出base case，就可以写出完整的递归解法。

这里的选择，其实对应的就是状态转移。