NC122题解 | #正则表达式匹配#

解法

• 根据动态规划
• 设置一个dp[m+1][n+1]的布尔数组，表示str的前m个字符与pattern的前n个字符是否匹配
• dp[0][0]初始化为true
• dp[0][]初始化：

		for(int i = 1; i <= n; i++){
            if(pattern[i-1] == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }

循环遍历匹配：由短到长 分三种情况：

• 1、最后一个字符相等str：aaa 与 pattern：cddda
• 2、最后一个字符是'.'
• 3、最后一个字符是'*':

此时前一个字符有3种情况：
	(1)前一个字符相等
	(2)前一个字符是'.'
	(3)前一个字符不是以上(无连续*) 

• 4、最后一个字符不是以上情况:fasle

		for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(pattern[j-1] == str[i-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else if(pattern[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(pattern[j-1] == '*'){
                    if(pattern[j-2] == str[i-1]){
                    	//也可以写成dp[i][j] = dp[i][j-2] || dp[i][j-1] ||dp[i-1][j];
                        dp[i][j] |= dp[i][j-2];//0次
                        dp[i][j] |= dp[i][j-1];//1次
                        dp[i][j] |= dp[i-1][j];//多次
                    }else if(pattern[j-2] == '.'){
                    	//也可以写成dp[i][j] = dp[i][j-2] || dp[i][j-1] ||dp[i-1][j];
                        dp[i][j] |= dp[i][j-2];//0次
                        dp[i][j] |= dp[i][j-1];//1次
                        dp[i][j] |= dp[i-1][j];//多次
                    }else{
                        dp[i][j] = dp[i][j-2];
                    }
                }else{
                    dp[i][j] =false;
                }
            }
        }