最容易理解的正则匹配
站长
· 阅读数 9
#题目描述
给你一个字符串 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 = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 4: 输入: s = "mississippi" p = "mis*is*p*." 输出: false 来源：力扣（LeetCode）
（题目著作权归领扣网络所有，力扣链接：leetcode-cn.com/problems/re…）
# 解题思路
1、根据规则p生成匹配图表；
2、根据图表去消耗待匹配的字符串
3、遇到*，查找出可匹配的字符有几个（count）
4、并从0到count开始递归消耗字符串，若全部返回false则为false，若有一个为true则视为次规则可以匹配此字符串；
# 思路图解
# 代码实现
// 生成匹配阵图
const toMatchArr = function(p){
// *处理
const matchArr = [];
p.forEach((item) =>{
if (item==='*') {
matchArr[matchArr.length-1] += '-*';
}else{
matchArr.push(item)
}
})
return matchArr;
}
// 寻找字符串出现的次数
const findCount = function(s,tar){
if(tar==='.') return s.length;
let count = 0;
while(tar === s[count]){
count++;
}
return count;
};
// 用匹配阵图消耗字符
const subStrWithMatch = function(s, matchArr){
// 以阵图匹配
while(matchArr.length){
const match = matchArr.shift();
if (match.length===1){
const sub = s.shift();
if (sub && (match[0]===sub || match[0]==='.')){
return subStrWithMatch(s, matchArr);
}else{
return false;
}
}else{
const count = findCount(s, match[0]);
if(count===0) continue;
let i = 0;
while(count>=i){
if (i) s.shift();
if (subStrWithMatch([...s], [...matchArr])){
return true;
}
i++;
continue;
}
return false;
}
}
if (s.length) return false;
return true;
}
// 入口方法
const isMatch = function(s, p) {
p = p.split('');
s = s.split('');
return subStrWithMatch(s, toMatchArr(p));
};