正则表达式匹配
题目:请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配。 1.如果pattern下一位是 *: 1.1 如果pattern 当前位和str 当前位匹配( *pattern ==*str || (*pattern =='.' && *str!=' ')) 则下一个状态可以是: <1>str前进一位 pattern 保持不变 <2>str前进一位pattern 前进两位 <3>str保持不变,pattern前进两位 1.2 如果不匹配,则下一个状态是: <1>str保持不变,pattern前进两位 2.如果pattern下一位不是*: 2.1 如果pattern 当前位和str 当前位匹配( *pattern ==*str || (*pattern =='.' && *str!=' ')) 则下一状态是: <1>str前进一位,pattern前进一位 2.2如果不匹配,则返回false 下面是实现代码
class Solution { public: bool match(char* str,char* pattern) { if(str ==NULL || pattern ==NULL) return true; return mymatch(str,pattern); } bool mymatch(char* str,char* pattern){ if(*str==' ' && *pattern ==' ') return true; if(*pattern ==' ' && *str!=' ') return false; if(*(pattern+1) =='*'){ if(*pattern == *str || (*pattern =='.' && *str!=' ')){ return mymatch(str+1,pattern) || mymatch(str+1,pattern+2) || mymatch(str,pattern+2); }else{ return mymatch(str,pattern+2); } } if(*str==*pattern || (*pattern=='.' && *str!=' ')) return mymatch(str+1,pattern+1); return false; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |