原题地址：正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "cab"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
具体到本题中，每次遇到*时就会产生多个分支，因为*意味着它前面的字符可以出现零次或任意多次，每一种选择就是一个分支。我们选择其中的任意一个分支往下走，如果走不通则退回到这个点，重新选择其它分支。
具体的实现代码如下：
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
const isMatch1 = function(s, p) {
// 空匹配串只能匹配空字符串
if (p.length === 0) {
return s.length === 0;
}
// 匹配第一个字符，注意.号可以当作任意字符使用
let firstMatch = s.length !== 0 && ['.', s[0]].includes(p[0]);
if (p.length > 1 && p[1] === '*') {
// *号表示前面这个字符可以出现零次或多次
// 零次相当于直接跳过这两个匹配字符
return isMatch1(s, p.substr(2)) || (firstMatch && isMatch1(s.substr(1), p));
}
return firstMatch && isMatch1(s.substr(1), p.substr(1))
};
测试：
let start = new Date();
const test = isMatch1;
console.log(test('aa', 'a')); // false
console.log(test('a', 'a*')); // true
console.log(test('ab', '.*')); // true
console.log(test('aab', 'c*a*b')); // true
console.log(test('mississippi', 'mis*is*p*.')); // false
console.log(new Date().getTime() - start.getTime()); // 6
动态规划
上面的回溯算法我们是采用递归来实现的，所以子串的匹配我们进行了多次重复的计算。优化也很简单，将子串的匹配结果先存储起来，下次需要用到这个结果时直接查询即可，这就是动态归划：
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
const isMatch2 = function(s, p) {
// 数组长度为p的长度加1，因为还要考虑空匹配串
const dp = new Array(p.length + 1);
// 要从后往前走，因为要从短的子串往长的匹配，这样长串匹配时才能用来短串的结果
for (let i = p.length; i >= 0; i --) {
// 也是长度加1
dp[i] = new Array(s.length + 1);
for (let j = s.length; j >= 0; j --) {
// 空匹配串的处理
if (i === p.length) {
dp[i][j] = (j === s.length);
continue;
}
// 这部分与回溯的逻辑相同，只是需要将匹配结果存储起来
let firstMatch = j !== s.length && ['.', s[j]].includes(p[i]);
if (i < p.length - 1 && p[i + 1] === '*') {
dp[i][j] = dp[i + 2][j] || (firstMatch && dp[i][j + 1]);
} else {
dp[i][j] = firstMatch && dp[i + 1][j + 1]
}
}
}
// 返回完整串的匹配结果
return dp[0][0];
};
测试：
let start = new Date();
const test = isMatch2;
console.log(test('aa', 'a')); // false
console.log(test('a', 'a*')); // true
console.log(test('ab', '.*')); // true
console.log(test('aab', 'c*a*b')); // true
console.log(test('mississippi', 'mis*is*p*.')); // false
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 双重遍历，时间复杂度为O(mn)，m和n分别为两个串的长度
空间复杂度： 也是O(mn)，因为需要用来二维数组来存储匹配结果
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019