LeetCode正则表达式——C

柔情只为你懂 2021-11-08 22:20 243阅读 0赞

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/regular-expression-matching][https_leetcode-cn.com_problems_regular-expression-matching]

## 题目描述 ##

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘\*’ 的正则表达式匹配。

'.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素

示例 1:  
输入:  
s = “aa”  
p = “a”  
输出: false  
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:  
输入:  
s = “aa”  
p = “a\*”  
输出: true  
解释: 因为 ‘\*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:  
输入:  
s = “ab”  
p = “.*"  
输出: true  
解释: ".*” 表示可匹配零个或多个（’\*’）任意字符（’.’）。

示例 4:  
输入:  
s = “aab”  
p = “c*a*b”  
输出: true  
解释: 因为 ‘\*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:  
输入:  
s = “mississippi”  
p = “mis*is*p\*.”  
输出: false

## 题解 ##

根据规则，**点好**匹配任意单个字符，**星号**匹配零个或多个前面的那一个元素。  
因为**字符一样**和**点号**都是一对一匹配，所以可以统一判断，但**星号**能够对应零个或很多，所以这里就有两种想法了。  
（1）**动态规划**  
第一种就是**星号**匹配归为一类，其它匹配归为一类，递归匹配，如果能够全部匹配，就返回真，否则假。  
（2）**二维数组**  
第二种就是以原字符串为行，匹配字符串为列，建立一个二维数组，把满足条件的位置定为真，最后能够使最后一个位置为真，就说明能够完全匹配。

s="aab"，p="c*a*b"

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]  
**或者调一下位置**

s="aaabc"，p="a*bc"

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

## 代码 ##

**1、第一种**

bool dp(int i,int j,char *s,char *p){
    	bool ans;
    	//完全匹配退出条件 
    	if(j == strlen(p) && i == strlen(s)){
    		ans = true;
    	}
    	else{
    		//判断第一个字符 
    		bool first_match = (i < strlen(s) && (p[j] == s[i] || p[j] == '.'));
    		//判断星号匹配 ，递归匹配 
    	    if (j + 1 < strlen(p) && p[j+1] == '*'){
    	        ans = (dp(i, j+2, s, p) || first_match && dp(i+1, j, s, p));
    	    }
    	    //点号匹配或一样或不一样 ，递归匹配 
    		else {
    	        ans = first_match && dp(i+1, j+1, s, p);
    	    }
    	}
    	return ans;
    }
    
    bool isMatch(char * s, char * p){
    	return dp(0,0,s,p);
    }

**2、第二种**

bool isMatch(char * s, char * p){
    	int row = strlen(s);	//行 
    	int col = strlen(p);	//列 
    	int i, j, ret;
    	//分配空间，全部初始化为 0 
    	int **dp = (int**)malloc(sizeof(int*)*(row+1));
    	for(i = 0; i < row+1; i++) {
    	      dp[i] = (int*)malloc(sizeof(int)*(col+1));
    		  memset(dp[i], 0, col+1);
    	}
    	//起始初始化为 1
    	dp[0][0] = 1;
    	//因为 '*' 匹配零个或多个前面的那一个元素，所以如果 s 没有，但 p 为 'p*' ，就还是为真 
    	for(j = 1; j < col+1; j++) {
          	if(p[j-1] == '*' && dp[0][j-2] == 1){
          		dp[0][j] = 1;
    		}
        }
    	//循环匹配 
    	for(i = 1; i < row+1; i++) {
    		for(j = 1; j < col+1; j++) {
    			// '.' 匹配任意单个字符
    			if(p[j-1] == '.' && dp[i-1][j-1] == 1) {
    			    dp[i][j] = 1;
    			} 
    			// '*' 匹配零个或多个前面的那一个元素
    			else if(p[j-1] == '*') {
    			    if(dp[i][j-2] == 1 || dp[i][j-1] == 1 || (dp[i-1][j] == 1 && (s[i-1] == p[j-2] || p[j-2] == '.'))){
    			    	dp[i][j] = 1;
    				}
    			}
    			// 字符一样 
    			else {
    			    if(dp[i-1][j-1] == 1 && s[i-1] == p[j-1]){
    			    	dp[i][j] = 1;
    				}
    			}
    	  	}
    	}
    	ret = dp[row][col];
    	//释放内存 
    	for(i = 0; i <= row; i++)
    	      free(dp[i]);
    	free(dp);
    	
    	return ret == 1;
    }

## 结果 ##

#include<stdio.h>
    #include<string.h>
    #include<malloc.h> 
    
    int main(){
    	char *s = (char *)"aab";
    	char *p = (char *)"c*a*b";
    	if(isMatch(s, p)==true){
    		printf("true");
    	}
    	else{
    		printf("false");
    	}
    	return 0;
    }

**第一种，运行速度较慢，但内存占用较小**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]  
**第二种，运行速度较快，但内存占用较大**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]

[https_leetcode-cn.com_problems_regular-expression-matching]: https://leetcode-cn.com/problems/regular-expression-matching
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211108/47f8a40c822e40cf8d91ed168bfeca0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211108/30082694eb704932b0a335eab5746aaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20211108/047373577e4a4cf29ccdfb7a955eeef5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: /images/20211108/357a909f517a48ba93dee988d15dd931.png