前言
- 个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
- 个人刷题练习系列专栏：个人CSDN牛客刷题专栏。 题目来自：牛客/题库 / 在线编程 / 剑指offer：
目录
- 前言
- 问题描述：
- 举例：
- 解法思路：
- 代码结果：
- 结束语
问题描述：
-
描述
请实现一个函数用来匹配包括’.‘和’‘的正则表达式。
1.模式中的字符’.‘表示任意一个字符
2.模式中的字符’'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配 -
数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ''。
3.0≤str.length≤26
4.0≤pattern.length≤26
举例：
//示例1：
//输入：
"aaa","a*a"
//返回值：
true
//说明：中间的*可以出现任意次的a，所以可以出现1次a，能匹配上
//==========================
//示例2：
//输入：
"aad","c*a*d"
//返回值：
true
//说明：因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。
//==========================
//示例3：
//输入：
"a",".*"
//返回值：
true
//说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）
//==========================
//示例4：
//输入：
"aad","c*a*d"
//返回值：
false
解法思路：
- 设有一个字符串aabc 以及一个匹配式：a*bc。按照递归的思想，我们的目的就是匹配完整的字符串，也就是第一个字符匹配成功 再匹配第二个字符 以此类推，直到匹配完成所有的字符。什么时候匹配结束呢？肯定某一个字符串为空 或者无法匹配的情况。因此进行以下情况的考虑：
case1：假设 表达式为空 匹配式也为空：显然匹配成功
case2：假设 表达式不为空，而匹配式为空：这种情况下显然 匹配失败。
case3：假设 表达式为空，而匹配式不为空：在这种情况下针对匹配式又有两种小的可能：
·case3.1 如果匹配式的样式为 abac这种字母和成对出现的情况，显然可以进行规约的，因此可以先判断是否偶数个字符，再根据舍弃前两个字符进行递归，最终会递归到case1的情况，说明匹配成功。
case4：假设 表达式不为空 匹配式也不为空：这种情况下，由于匹配式中*的存在，造成干扰，需要分两种情况来考虑：
case4.1 假设匹配式的第二个字符不是*，这样说明匹配式的第一个字符固定了，直接和表达式第一个字符比较，然后都右移一位递归即可。
case4.2：假设匹配式的第二个字符是*，如果第一个字符能匹配上说明：匹配式可以抵消前两个字符，也可以单方面抵消表达式的一个字符，因此可以做一个或运算的递归。如果匹配不上，说明匹配式只能舍弃前两个字符，再进行递归。
代码结果：
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str string字符串 * @param pattern string字符串 * @return bool布尔型** C语言声明定义全局变量请加上static，防止重复定义*/
//一个递归的方式 从前到后进行字符串匹配
bool match_str(char *str, char *pattern){//递归的终止条件 某个字符串为空//1. 都为空 明显匹配成功int a;if(*str=='\0'&&*pattern=='\0')return true;//2. pattern为空 str不为空 明显匹配失败else if(*str!='\0'&&*pattern=='\0')return false;//3. str为空 pattern 不为空,这个时候 只有形如 a*b*c*的才能匹配成功 否则匹配失败//可以继续递归 抵消一对 a*else if(*str=='\0'&&*pattern!='\0'){//必须偶数个if(strlen(pattern)%2==0){//判断前两个字符是否为 a*样式if(pattern[0]!='*'&&pattern[1]=='*')//抵消两个字符后递归return match_str(str,&pattern[2]);elsereturn false;}else return false;}//4. 两个字符串都不为空 考虑pattern的第二个字符是否为*else{//4.1 pattern的第二个字符不是* 说明只有第一个字符匹配才能进行递归if(pattern[1]!='*'){//第一个字符匹配成功 均右移一个字符匹配if(str[0]==pattern[0]||pattern[0]=='.')return match_str(&str[1], &pattern[1]);//第一个字符匹配失败 返回失败elsereturn false;}// pattern的第二个字符是 * 此时判断第一个字符是否匹配 else{//第一个字符也匹配上了 说明可以舍弃匹配式的两个字符 也可以舍弃一个字符串的字符if(str[0]==pattern[0]||pattern[0]=='.')return (match_str(&str[0], &pattern[2])||match_str(&str[1], &pattern[0]));//说明第一个字符没有匹配上 这时候必须舍弃掉匹配式的前两个字符b* else{return match_str(str, &pattern[2]);}}}
}
bool match(char* str, char* pattern ) {// write code hereif(str==NULL||pattern==NULL)return false;return match_str(str,pattern);}
结束语
- 以上就是该C语言编程题的内容。可以在牛客尝试刷几道题目来练习实践。牛客网刷题(点击可以跳转)，可以尝试注册使用。
- 题目来自：牛客/题库 / 在线编程 / 剑指offer：
本文链接：https://my.lmcjl.com/post/5618.html
展开阅读全文
4 评论