题目描述
请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符,而’*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
示例1
输入
“aaa”,“a*a”
返回值
true
思路以及解答
这道题,仔细一想,感觉情况很多,很凌乱,此处介绍的是递归的做法,其实本题还可以使用动态规划。最重要的是需要分类讨论,原串定义为str
,模式串为pattern
。`
- 如果
pattern
长度为0- 且
str
长度为0
,说明刚刚好匹配完,返回ture
str
长度不为0
,说明没有匹配完,返回false
- 且
- 如果
pattern
的长度大于0- 分为两种情况讨论,一种是直接把
*
和*
前面的字符去掉,相当于匹配了0
个,然后接着比较;另外一种是,如果str
的长度大于0
,并且第一个字符匹配,那就把str
的第一个字符去掉,两者接着匹配。 - 如果
pattern
的长度大于1
,且第2
个字符是*
,说明前面的字符可以匹配0
,1
或者多次 - 否则,说明第二个字符不是
*
,那么就直接比较第一个字符是不是匹配,同时将后面的字符进行匹配。
- 分为两种情况讨论,一种是直接把
注意:上面说的第一个字符是不是匹配,除了两个字符相等的情况,其实还有模式串的字符为’.
'的情况。
public boolean match(String str, String pattern) { if (pattern.length() == 0) { return str.length() == 0; } // 第二个字符是'*' if (pattern.length() > 1 && pattern.charAt(1) == '*') { // 匹配0次,直接把'*'去掉,两者判断 return match(str, pattern.substring(2)) // 第一个字符相同的时候,去掉第一个字符,判断后面的(相当于匹配多次) || (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern); } else { // 第二个字符不是 '*'的时候,判断第1个字符是否相同,相同的时候再从第2位开始比较 return str.length() > 0 && firstSame(str, pattern) && (match(str.substring(1), pattern.substring(1))); } } // 判断第一个字符是不是相同 private boolean firstSame(String s, String p) { // 两个相同,或者有一个是"." return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'; }
当然,这种做法不是最优的,使用了大量的递归操作,并且重复递归,时间复杂度比较高。
当然,这道题还有一个更优的做法,但是过程咋一看有点复杂,我们可以来分析一下,主要思路是动态规划:
-
首先我们需要定义状态:用一个二维数组(套路)
dp[i][j]
用来表示str
的前i
个字符和pattern
的前j
个字符是否匹配。 -
接下来,我们需要初始化简单状态,因为想要求后面的状态,是依赖于前面的状态的,一般是初始化
dp[i][j]
的首行和首列。
dp[0][0]= true
,表示两个空的字符串是匹配的。dp
数组的首列,除了dp[0][0]
为true
,其他的都是false
。因为pattern为空,但是s不为空的时候,肯定不匹配。dp
的首行,也就是str为空的时候,如果pattern的偶数位都是“*”,那么就可以匹配,因为可以选择匹配0次。
初始化前面之后,后面的从索引1
开始匹配:
- 2.1 如果
dp[i - 1][j - 1]=true
andstr[i - 1] == pattern[j - 1]
时,则dp[i][j]=true
。(也就是前面匹配,接下来的字符一样匹配) - 2.2 如果
dp[i - 1][j - 1]=true
且pattern[i-1]=='.'
,那么dp[i][j]=true
。(其实也是.
可以匹配任何字符)
- 1.1 如果
dp[i][j-2]==true
,那么dp[i][j]=true
(相当于str的前i和pattern的前j-2个字符匹配,此时的*
前面的那个字符出现了0
次)。 - 1.2 如果
dp[i-1][j]==true
且str[i-1]==pattern[j-2]
,则dp[i][j] =true
。(如果str
的前i - 1
个字符和pattern
的前j
个字符匹配,并且str
的第i
个字符和pattern
的第j - 1
个字符相等,相当于‘*
’前面的字符出现了1
次) - 1.3 如果
dp[i-1][j]=true
且pattern[j-2]=='.'
的时候,则dp[i][j]=true
。(表示str
的前i-1
个和patten
的前j
个匹配,并且pattern
的第j-1
个是‘.
’,第j
个是‘*
’,那么说明可以匹配任何字符任何次数,自然str
可以多匹配一个字符。)
pattern
的第j
个字符不为“*
”(即是pattern[j-1]!='*'
)pattern
的第j
个字符为“*
”(即是pattern[j-1]=='*'
)
处理完数组之后,最后返回dp[n-1][m-1]
,也就是str
的前n
个和pattern
的前m
个字符是否匹配。
public boolean match(String str, String pattern) { if (pattern.length() == 0) { return str.length() == 0; } int n = str.length() + 1; int m = pattern.length() + 1; boolean[][] dp = new boolean[n][m]; dp[0][0] = true; for (int j = 2; j < m; j = j + 2) { if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') { dp[0][j] = true; } } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (pattern.charAt(j - 1) == '*') { dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.'); } else { dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'); } } } return dp[n - 1][m - 1]; }
时间复杂度 O(mn)
: 其中 m
,n
分别为 str
和 pattern
的长度,状态转移需遍历整个 dp
矩阵。
空间复杂度 O(mn)
: 状态矩阵 dp
使用 O(mn)
的额外空间。