首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配
  • 热度指数:90543 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次(包含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 '*'。
3.
4.


示例1

输入

"aaa","a*a"

输出

true

说明

中间的*可以出现任意次的a,所以可以出现1次a,能匹配上              
示例2

输入

"aad","c*a*d"

输出

true

说明

因为这里 c 为 0 个,a被重复一次, * 表示零个或多个a。因此可以匹配字符串 "aad"。              
示例3

输入

"a",".*"

输出

true

说明

".*" 表示可匹配零个或多个('*')任意字符('.')              
示例4

输入

"aaab","a*a*a*c"

输出

false
分享解题思路:
特色:短!
bool match(char* str, char* pattern ) {
    if (pattern[0] && pattern[1] == '*') pattern[1] = pattern[0] - 'a' + 'A';
    if (!pattern[0])return str[0] == 0;
    else if (pattern[0] >= 'A' && pattern[0] <= 'Z' || pattern[0]=='.'-'a'+'A') return ((pattern[0]=='.'-'a'+'A' || str[0] == pattern[0] - 'A' + 'a') && (str[0] && (match(str + 1, pattern) || match(str + 1, pattern + 1)))) || match(str, pattern+1);
    else return ((pattern[0] == str[0] || (str[0] && pattern[0] == '.')) && str[0] && match(str + 1, pattern + 1)) || ((pattern[1] >= 'A' && pattern[1] <= 'Z' || pattern[1]=='.'-'a'+'A') && match(str, pattern+2));
}


发表于 2023-03-09 11:20:14 回复(0)
剑指offer解法,用C++会超内存,所以用C通过
(递归深度大,使用内存多(C++对象也会占内存),所以部分测试用例会超时,如:"aaaaaaaaaaaaab""a*a*a*a*a*a*a*a*a*a*c"。)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @param pattern string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
#include<stdbool.h>
 bool matchCore(char*str,char*pattern)
    {
        //字符串以\0结尾
        if(*str=='\0'&& *pattern=='\0')
            return true;//都到尾巴了,说明前面都匹配上了true
        if(*str!='\0'&& *pattern=='\0')
            return false;//pattern没了,str还有,说明对不上了
        if(*(pattern+1)=='*')
        {
            if(*pattern==*str||(*pattern=='.'&& *str!='\0'))
            {//str没到结尾说明还可以往下走
                return matchCore(str+1, pattern+2)//*把前面那个定住了,自己消失了
                    ||matchCore(str+1, pattern)//*把前面那个变成两个,pattern还是前面那个字符
                    ||matchCore(str, pattern+2);//*把前面的全干没了,往下走
            }
            else{
                return matchCore(str, pattern+2);//*把前面的全干没了,往下走
            }
        }
        if(*str==*pattern||(*pattern=='.'&& *str!='\0'))
            return matchCore(str+1, pattern+1);//正常往下走
        return false;
    }
bool match(char*str, char*pattern) {
        // write code here
        if(str==NULL||pattern==NULL)
            return false;
        return matchCore(str,pattern);
    }
   

发表于 2022-04-02 23:37:01 回复(0)