手机网站开发总结,深圳家装,网站做编辑器,宁波网站建设服务电话小编在求职找找工作期间剑指offer上的算法题刷了很多遍#xff0c;并且每道题小编当时都总结了一种最适合面试时手撕算法的最优解法。考虑到剑指offer算法题在面试中的高频出现#xff0c;小编每天和大家分享一道剑指offer上的算法题#xff0c;以及小编总结的答案。下面是第… 小编在求职找找工作期间剑指offer上的算法题刷了很多遍并且每道题小编当时都总结了一种最适合面试时手撕算法的最优解法。考虑到剑指offer算法题在面试中的高频出现小编每天和大家分享一道剑指offer上的算法题以及小编总结的答案。下面是第052是道剑指offer算法题题目描述请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符而*表示它前面的字符可以出现任意次(包含0次)。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串aaa与模式a.a和ab*ac*a匹配但是与aa.a和ab*a均不匹配分析题解在注释中相对之前的题目这道题难度更大些。/* 解这题需要把题意仔细研究清楚反正我试了好多次才明白的。 首先考虑特殊情况 1两个字符串都为空返回true 2当第一个字符串不空而第二个字符串空了返回false(因为这样就无法 匹配成功了,而如果第一个字符串空了第二个字符串非空还是可能匹配成 功的比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次 所以有可能匹配成功) 之后就开始匹配第一个字符这里有两种可能匹配成功或匹配失败。但考虑到pattern 下一个字符可能是‘*’ 这里我们分两种情况讨论pattern下一个字符为‘*’或 不为‘*’ 1pattern下一个字符不为‘*’这种情况比较简单直接匹配当前字符。如果 匹配成功继续匹配下一个如果匹配失败直接返回false。注意这里的 “匹配成功”除了两个字符相同的情况外还有一种情况就是pattern的 当前字符为‘.’,同时str的当前字符不为‘\0’。 2pattern下一个字符为‘*’时稍微复杂一些因为‘*’可以代表0个或多个。 这里把这些情况都考虑到 a当‘*’匹配0个字符时str当前字符不变pattern当前字符后移两位 跳过这个‘*’符号 b当‘*’匹配1个或多个时str当前字符移向下一个pattern当前字符 不变。(这里匹配1个或多个可以看成一种情况因为当匹配一个时 由于str移到了下一个字符而pattern字符不变就回到了上边的情况a 当匹配多于一个字符时相当于从str的下一个字符继续开始匹配) 之后再写代码就很简单了。*/class Solution {public: bool match(char* str, char* pattern){ if (*str \0 *pattern \0) return true; if (*str ! \0 *pattern \0) return false; //if the next character in pattern is not * if (*(pattern1) ! *) { if (*str *pattern || (*str ! \0 *pattern .)) return match(str1, pattern1); else return false; } //if the next character is * else { if (*str *pattern || (*str ! \0 *pattern .)) return match(str, pattern2) || match(str1, pattern); else return match(str, pattern2); } }};猜你还想看一个程序员写多门语言写代码时会记串么计算机专业学生最应该学习的课程前五位是什么长按扫码关注及时收看更多精彩内容博主今日头条大数据工程师专注求职 面经 源码 java 大数据技术分享点击”阅读原文“领取5T精品资料面试总结、100实战项目我知道你 “在看”
