【剑指】62，正则表达式（有无）

旧城等待， 2023-07-14 08:22 20阅读 0赞

**题目描述**  
请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab\*a"均不匹配

思路：  
首先，我们判断是不是到了模式串的尾部，如果是，并且此时str原生串到了尾部，那么返回真，否则返回假。  
然后我们判断此时的模式串的p的下一个字符是不是 \* ，因为这个会影响当前的匹配，所以他要先做。如果下一个不是 即 p+1！=’*’ ，，说明不用考虑当前个出现任意次，直接p和s当前比对。或模式串p位 . 且字符串s不为‘\\0’，那就不说了，直接下一个字符对比。否则，false；  
但是如果p+1==‘*’了，说明当前的字符p可以多个或0.此时我们用while循环，p和s相等的话，或者p位‘ . ’并且s！=‘\\0’了 ： 此时判断将此时的p往后移动两个点（x\*）后还真吗，真就返回true，否则就将s++，继续往后匹配，然后将p移动两个位。

代码：

class Solution { 
    public:
        bool match(char* str, char* pattern)
        { 
          return   ismatch(str, pattern);
        }
         private:
        bool ismatch(const char* s,const char* p)
        { 
    	if(*p=='\0')
    		return *s=='\0';
    	if(*(p+1)!='*')
    	{ 
    		if(*p==*s || (*p=='.' &&*s !='\0')
    			return ismatch(s+1,p+1);
    		else
    			return false;
    	}
    	else
    	{ 
    		while(*p===*s || (*p=='.' && *s!='\0') )	//此时，是p模式串的第二个是*，。进入循环，如果当前p==s，或者p任意了，s不为空，那就判断p+2之后为真吗。为就是true。。。然后s++继续走
    		{ 
    			if(ismatch(s,p+2)
    				return true;
    			s++;
    		}
    		return ismatch(s,p+2)
    	}
    
    	}