题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"aba"均不匹配
思路
使用动态规划求解:
1.开辟一个二维数组 dp[i][j]来存放模式串的前j个元素与字符串的前i个元素是否匹配 初始化dp[0][0]为true(表示两个空串是匹配的)
2.如果第j个元素不是 那么采用正常的匹配方式即模式串的第j个元素与字符串的第i个元素一样,或者模式串的第j个元素是‘.’,dp[i][j]=dp[i-1][j-1]
3.如果第j个元素是,那么分两种情况有一种情况为true即可
第一种将()和前面那个元素视为空串(这时号代表出现0次)那么dp[i][j-2]==true即表示匹配成功
dp[i][j] = dp[i][j-2]
第二种 dp[i][j-2]!=true 那么就得是得第i个元素与第j-1个元素相等(此时代表的是出现1次)或者第j-1个元素是‘.’ 并且dp[i-1][j]=true即可
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ //使用动态规划求解 public boolean match (String str, String pattern) { // write code here int s = str.length(); int p = pattern.length(); boolean[][] dp = new boolean[s+1][p+1];//00 用于存放两个空字符串的结果 dp[i][j] 表示模式串前j个是否与字符串前i个匹配 for(int i = 0;i<=s;i++){//实际上模式串和字符串的起点为1(所以后面的下标都是i-1 j-1) for(int j =0;j<=p;j++){ if(j==0){ dp[i][j]=(i==0);//只有字符串和模式串都为空的时候才匹配,当模式串为空,字符串不为空则返回false }else{ if(pattern.charAt(j-1)!='*'){//如果第j-1个字符不是* if(i>0&&(str.charAt(i-1)==pattern.charAt(j-1)||pattern.charAt(j-1)=='.')){ //正常匹配 dp[i][j] = dp[i-1][j-1]; } }else{//如果第j个是* 那么分两种情况,有一种成立即可 //case 1 可以直接忽略*前模式的那个元素(*代表出现0次 比如a* 这两个元素做空字符串) // 那么dp[i][j]==true 只需满足 dp[i][j-2]==true即可 if(j>=2){ dp[i][j] = dp[i][j-2]; } //case 2 如果dp[i][j-2]不等于true那么要满足第j-1个字符(这个字符也可以为‘.’)与第i个字符匹配即可 //下标多减1是因为dp是从1开始记录的 if(i>0 && j>=2 &&(str.charAt(i-1)==pattern.charAt(j-2)||pattern.charAt(j-2)=='.')){ dp[i][j] |= dp[i-1][j];//使用或等于 两种情况有一种符合就行 } } } } } return dp[str.length()][pattern.length()];