本文共 1377 字，大约阅读时间需要 4 分钟。

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

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 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 = “cab”

输出：true

解释：因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5：

输入：s = “mississippi” p = “misisp*.”

输出：false

class Solution {
   	    public boolean isMatch(String s, String p) {
   	    	char[] str = s.toCharArray(), ptr = p.toCharArray();	    	// 动态规划	    	boolean[][] dp = new boolean[s.length()+1][p.length()+1];	    	// 初始化	    	dp[0][0] = true;	    	// 开始遍历 j为空字符串无意义 p[j-1]表示的是状态dp[i][j]下的p的最后一个字符	    	for(int i=0;i<=str.length;i++) {
   	    		for(int j=1;j<=ptr.length;j++) {
   	    			// 判断p的 字符串是否为*	    			if(ptr[j-1]!='*') {
   	    				//再次进行判断	    				if(i>0&&(str[i-1]==ptr[j-1]||ptr[j-1]=='.')) {
   	    					dp[i][j] = dp[i-1][j-1];	    				}	    			}else {
   	    				// 0次或多次	    				if(j>1) {
   	    					// 不看即0次	    					dp[i][j] |= dp[i][j-2];	    				}	    					    				//看了多次	    				if(i>0&&j>1&&(str[i-1]==ptr[j-2]||ptr[j-2]=='.')) {
   	    					dp[i][j] |= dp[i-1][j];	    				}	    			}	    		}	    	}	    		    	return dp[s.length()][p.length()];	    }	}

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111748586 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！