题目描述:请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
问题分析:首先来看匹配完全的必要条件,就是模式串遍历完,同时原字符串也遍历完。据此,可以从前往后依次匹配直到匹配完全。由于’.’表示任意字符,因此可与任意字符匹配,可看作原串当前遍历到的字符。而’*‘的匹配结果则与‘*’前的字符有关,所以对于模式串当前字符下一位是不是‘*’,可分为两种情况:
(1)当前字符下一位不是‘*’:
? ? ? ? 这里又分为两种情况:
? ? ? ? 1o 当前字符匹配。那么原串和模式串都向后移一位,例如:
? ? ? 2o 当前字符不匹配。那么直接返回false,例如:
(2)当前字符下一位不是‘*’:
? ? 1o 当前字符不匹配。那么为了尽可能进行匹配,就要去除模式串的当前字符,去判断其后面的字符,也就是模式串向后移两位,例如:
? ? 2o 当前字符匹配:此时有多种情况
? ? ? ? ? ·1.‘*’表示前面的字符出现0次:那么原串不移动,模式串向后移两位。如 aab/aa*ab? (加粗的为当前字符)
? ? ? ? ? ·2.‘*’表示前面的字符出现1次:那么原串向后移一位,模式串向后移两位。如aab/aa*b
? ? ? ? ? ·3.‘*’表示前面的字符出现n次(n>1):那么原串向后移一位,模式串不移动。如aaa/aa*
? ? 只要上面三种情况的任意一种匹配成功即可
代码截图:
这里要注意条件判断的先后顺序,首先判断索引是否超过长度,不然会导致越界的错误