这题是剑指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断点调试效率更高。
网友评论