Regular Expression Matching

简单的正则匹配算法:

栗子🌰

s = "aa"
p = "a"
Output: false

s = "aa"
p = "a*"
Output: true

s = "ab"
p = ".*"
Output: true

s = "aab"
p = "c*a*b"
Output: true

s = "aaa"
p = "a*a"
Output: true

先分析一下两个正则符号, '.'是可以表示任何字符的, 做特殊判断就好, 但是'*'需要和前面的字符连在一起, 表示前面一个字符出现0或多次, 那算法按照p[j+1]是否为'*'的两种情况展开

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    return match(s, p, 0, 0)
};
function match(s, p, i, j) {
    if(j==p.length){//如果p遍历完了s没遍历完, 就是不匹配, 反过来不一定(例如p以'*'结尾)
        return i==s.length;
    }
    if(j==p.length-1||p[j+1]!='*'){//p越界情况处理一下, 然后开始以'*'分情况
        if(i==s.length||(p[j]!='.'&&p[j]!=s[i])){//p有一个未匹配的非'*', 和正常不匹配, 返回false
            return false;
        } else {
            return match(s, p, i+1, j+1)
        }
    }
    //p[j+1]=='*'
    while(i < s.length&&(s[i]==p[j]||p[j]=='.')){
        if(match(s, p, i, j+2)){//提前判断一下, 防止s='aaa', p='a*a'这种情况
            return true
        }
        i++//正常匹配向后遍历
    }
    return match(s, p, i, j+2)//找完了, 下一个递归
}