剑指offer52：正则表达式匹配

1 题目描述

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

2 思路和方法

　　正则表达式中有三种情况：
　　a.普通字符
　　b.字符’.’
　　c.普通字符或’.’ + 字符’*’

　　碰到情况a、b都直接对比可以匹配，
　　难点在于处理情况c
　　情况c可以分两种子情况处理：
　　c1.字符串的首字母与模式的首字母不匹配，模式直接右移两格（相当于’*’前面的字符出现了0次）
　　c2.字符串的首字母与模式的首字母匹配，则：
　　　　字符串右移一格，模式不移动（’*’前面的字符出现了不止一次）
　　　　或字符串右移一格，模式右移两格（’*’前面的字符出现了刚好一次）
　　　　或字符串不移动，模式右移两格（’*’前面的字符出现了0次）

　　当字符串和模式同时走到结尾+1的位置，则表示匹配
　　当字符串走到结尾+1的位置，模式还没走到结尾+1的位置，还要继续匹配（因为模式后面可能还有a*b*可以匹配0个字符串）
　　当字符串还没走到结尾+1的位置，模式走到结尾+1的位置，则表示不匹配

3 C++核心代码

 class Solution {

 public:

     bool match(char* str, char* pattern) {

         if(str == nullptr && pattern == nullptr)

             return true;

         return matchCore(str, pattern);

     }

     bool matchCore(char* str, char* pattern){

         if(*str == '\0' && *pattern == '\0')    //

             return true;

         if(*str != '\0' && *pattern == '\0')    //

             return false;

         if(*(pattern+) == '*'){

             // 当前字符匹配

             if( *pattern == *str || (*pattern == '.' && *str!='\0')){

                 return matchCore(str+, pattern)      //str字符串右移一格，（’*’前面的字符出现了不止一次）模式不移动

                     || matchCore(str+, pattern+)    //str或字符串右移一格，模式右移两格（’*’前面的字符出现了刚好一次），模式状态改变

                     || matchCore(str, pattern+);     //str或字符串不移动，模式右移两格（’*’前面的字符出现了0次）忽略*字符

             }

             else

                 return matchCore(str, pattern+);    // 当前字符不匹配 忽略 *

         }

         // 逐个字符匹配

         if(*str == *pattern || (*pattern == '.' && *str!='\0'))

             return match(str+,pattern+);

         return false;

     }

 };

参考资料

https://blog.csdn.net/zjwreal/article/details/89055244（代码）

https://blog.csdn.net/u013908099/article/details/85954619（思路）

https://blog.csdn.net/qq1263292336/article/details/75734596（思路）

巴特西

剑指offer52：正则表达式匹配

1 题目描述

2 思路和方法

3 C++核心代码

参考资料

最新文章

热门文章