题目
请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配
思路
本题的难点在于*的处理。碰到*需要判断*前的字符是否匹配，应该匹配几个的问题。既然需要判断*前的字符，那我们在循环处理的时候就，需要能访问到*前的字符，所以我们在比较某个字符的时候，先判断下一个字符是否为*
使用递归，将s和pattern字符串一个个字符进行比对，当比对到某个字符时候，判断下一个字符是否为*
下一个字符不是号，则正常处理，判断当前是否相等，相等则进入下一个字符，不相等则正则匹配失败
下一个字符是号，可以分为两种情况，
当前字符不相等，不相等则，pattern直接跳过两个字符
相等，则考虑匹配0个或1个字符，再继续递归进去，这样就可以考虑所有情况了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
function match (s, pattern) {
if (s.length === 0 && pattern.length === 0) return true
else if (s.length !== 0 && pattern.length === 0) return false
else {
if (pattern[1] !== '*') {
if ((s.length > 0 && pattern[0] === '.') || s[0] === pattern[0]) {
return match(s.substring(1), pattern.substring(1))
} else {
return false
}
} else {
if ((s.length > 0 && pattern[0] === '.') || s[0] === pattern[0]) {
return match(s, pattern.substring(2)) || match(s.substring(1), pattern)
} else {
return match(s, pattern.substring(2))
}
}
}
}
|
