JavaScript算法——正则表达式匹配

这题是剑指offer上的，我弄了一段时间才想清楚逻辑。

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

//s, pattern都是字符串
function match(s, pattern)
{
    
}

解这题只需要几行代码：

//s, pattern都是字符串
function match(s, pattern)
{
    var reg=new RegExp("^" + pattern + "$");
    return reg.test(s);
}

利用了JS自带的RegExp对象，但这样做对自身技术不会有提高，所以我们得思考如何不用库函数解题

思路

两个参数s和pattern都为字符串，根据题目意思，我们要做的就是比较这两个字符串是否相等。但我们不能直接简单的做比较，因为第二个字符串中出现 . 和 * 时有特殊作用，例如aaa和a*这两个字符串是相等的

一.特殊情况

• s和pattern都为空，必定匹配，返回true
• s非空，而pattern空，返回false
• 而如果s空，pattern非空，返回true还是false呢？
  答案是：不一定
  例如第二个字符串为aaa*，还是会匹配成功，因为a可以出现0次。

二.通用情况

考虑完特殊情况，我们开始匹配第一个字符，匹配只有两种可能，匹配成功或是失败。
考虑到pattern下一个字符可能是*，我们分两种情况讨论

• pattern下一个字符为*
• pattern下一个字符不为*

1. pattern下一个字符不为*

这种情况比较简单，直接比较当前字符是否相等，相等则继续匹配下一个（递归），不相等返回false。
注意 这里的相等除了两个字符相同(a===a)这种情况，还有一种情况，就是pattern的当前字符为.，且s的当前字符不为空白符

2. pattern下一个字符为*

这种情况复杂些，因为*可以代表0个、1个或多个。可分两种情况考虑

(1 )*匹配0个字符

str当前字符不变，pattern当前字符后移两位，跳过当前字符和*

(2) *匹配1或n个字符

str当前字符移向下一个，pattern当前字符不变，不匹配时又回到（1）
不变。

这里为什么没有分三种情况呢？
因为匹配1个和多个是可以合并的，例如ab和ab，匹配第一个字符，a与a相同，第一个字符串后移一位变成b，而第二个字符串不变仍为a，b!=a，不匹配，又回到第一步，匹配0个字符，第一个字符串保持不变仍为b，第二个字符串后移两位，即跳过a和，变成b。此时b=b，匹配成功。

代码如下：

istr和ipattern表示字符串下标，如s[0]表示字符串s第一个字符,初始值为0

function matchCore(s,istr,pattern,ipattern) {
    //两个字符串都为空
    if(istr===s.length&&ipattern===pattern.length){
        return true;
    }

    //第一个不空，而模式空返回false
    if(istr!=s.length&&ipattern===pattern.length){
        return false;
    }
    //模式的下一个字符串为*，前一个字符串可出现任意次
    if(pattern[ipattern+1]==='*'){
        //匹配成功分两种情况，1-字符串相等，2-模式字符串为'.'表示任意字符且s不为空字符
      
        if(s[istr]===pattern[ipattern]||(pattern[ipattern]==='.'&&istr!=s.length)){
        
            return  matchCore(s,istr,pattern,ipattern+2) ||matchCore(s,istr+1,pattern,ipattern);
        }
        //匹配失败，模式+2，字符串不动
        return matchCore(s,istr,pattern,ipattern+2);
    }
    //下一个字符不是*，匹配成功则都加1
    if(s[istr]===pattern[ipattern]||(pattern[ipattern]==='.'&&istr!=s.length)){
        return matchCore(s,istr+1,pattern,ipattern+1);
    }
    return false;
}
function match(s, pattern)
{
     if(s==null||pattern==null){
        return false;
    }
    return matchCore(s,0,pattern,0);
}

总结

解决问题前先梳理好逻辑与思路，切忌上来就写代码。可以拿草稿纸写写思路或是画画流程图，逻辑清晰，代码就不难写了，写完代码后难免遇到bug，这时候不能停留在console.log()，用debug断点调试效率更高。