题目:正则表达式匹配
请实现一个函数用来匹配包括’.’和’ ‘的正则表达式。模式中的字符’.’表示任意一个字符,而’ ‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。
举例说明
例如,字符串”aaa”与模式”a.a”和”ab ac a”匹配,但与”aa.a”和”ab * a”均不匹配
思路
- 递归实现
- 分清模式字符串pattern和待匹配字符串Str。匹配是指Str的所有字符匹配整个pattern。
- 每次从Str里拿出一个字符和pattern中的字符去匹配,主要的核心是判断pattern当前字符是否是”*”。
- 设匹配递归函数 match(str, pattern)
对每一个字符
- 一对一匹配 :如果模式匹配字符的下一个字符不是”*”
1)如果pattern中的字符ch是’.’,那么它可以匹配Str中的任意字符;
2)如果pattern中的字符ch不是’.’,但Str中的字符是ch,则它们同样相互匹配
匹配则在Str和pattern上都向后移动一个字符,也就是match(str+1, pattern+1),接着匹配后面的字符。
否则则直接返回false。 - 一对多匹配:如果模式匹配字符的下一个字符是”*”
1 | public class _19 { |