题目主要信息:
- 一个正常字符串str,可能为空,只包含小写字母
- 一个模式串pattern,可能为空,只包含小写字母和‘*’与‘.’
- 模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)
- 求str与pattern是否能完全匹配
举一反三:
学习完本题的思路你可以解决如下题目:
方法:动态规划(推荐使用)
知识点:动态规划
动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果
思路:
如果是只有小写字母,那么直接比较字符是否相同即可匹配,如果再多一个'.',可以用它匹配任意字符,只要对应str中的元素不为空就行了。但是多了'*'字符,它的情况有多种,涉及状态转移,因此我们用动态规划。
具体做法:
-
step 1:设
dp[i][j]
表示str前i个字符和pattern前j个字符是否匹配。(需要注意这里的i,j是长度,比对应的字符串下标要多1) -
step 2: (初始条件) 首先,毋庸置疑,两个空串是直接匹配,因此。然后我们假设str字符串为空,那么pattern要怎么才能匹配空串呢?答案是利用'*'字符出现0次的特性。遍历pattern字符串,如果遇到'*'意味着它前面的字符可以出现0次,要想匹配空串也只能出现0,那就相当于考虑再前一个字符是否能匹配,因此。
-
step 3: (状态转移) 然后分别遍历str与pattern的每个长度,开始寻找状态转移。首先考虑字符不为'*'的简单情况,只要遍历到的两个字符相等,或是pattern串中为'.'即可匹配,因此最后一位匹配,即查看二者各自前一位是否能完成匹配,即。然后考虑'*'出现的情况:
pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]
:即pattern前一位能够多匹配一位,可以用'*'让它多出现一次或是不出现,因此有转移方程- 不满足上述条件,只能不匹配,让前一个字符出现0次,.
图示:
Java实现代码:
import java.util.*;
public class Solution {
public boolean match (String str, String pattern) {
int n1 = str.length();
int n2 = pattern.length();
//dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
boolean[][] dp = new boolean[n1 + 1][n2 + 1];
//遍历str每个长度
for(int i = 0; i <= n1; i++){
//遍历pattern每个长度
for(int j = 0; j <= n2; j++){
//空正则的情况
if(j == 0){
dp[i][j] = (i == 0 ? true : false);
//非空的情况下 星号、点号、字符
}else{
if(pattern.charAt(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{
//碰到*
if(j >= 2){
dp[i][j] |= dp[i][j - 2];
}
//若是前一位为.或者前一位可以与这个数字匹配
if(i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')){
dp[i][j] |= dp[i - 1][j];
}
}
}
}
}
return dp[n1][n2];
}
}
C++实现代码:
class Solution {
public:
bool match(string str, string pattern) {
int n1 = str.length();
int n2 = pattern.length();
//dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false));
//两个都为空串自然匹配
dp[0][0] = true;
//初始化str为空的情况,字符串下标从1开始
for(int i = 2; i <= n2; i++){
//可以让自己前面个字符重复0次
if(pattern[i - 1] == '*')
//与再前一个能够匹配空串有关
dp[0][i] = dp[0][i - 2];
}
//遍历str每个长度
for(int i = 1; i <= n1; i++){
//遍历pattern每个长度
for(int j = 1; j <= n2; j++){
//当前字符不为*,用.去匹配或者字符直接相同
if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])){
dp[i][j] = dp[i - 1][j - 1];
//当前的字符为*
}else if(j >= 2 && pattern[j - 1] == '*'){
//若是前一位为.或者前一位可以与这个数字匹配
if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])
//转移情况
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
else
//不匹配
dp[i][j] = dp[i][j - 2];
}
}
}
return dp[n1][n2];
}
};
Python代码实现:
class Solution:
def match(self , str: str, pattern: str) -> bool:
n1 = len(str)
n2 = len(pattern)
#dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
dp = [[False] * (n2 + 1) for i in range(n1 + 1)]
#两个都为空串自然匹配
dp[0][0] = True
#初始化str为空的情况,字符串下标从1开始
for i in range(2, n2 + 1):
#可以让自己前面个字符重复0次
if pattern[i - 1] == '*':
#与再前一个能够匹配空串有关
dp[0][i] = dp[0][i - 2]
#遍历str每个长度
for i in range(1, n1 + 1):
#遍历pattern每个长度
for j in range(n2 + 1):
#当前字符不为*,用.去匹配或者字符直接相同
if pattern[j - 1] != '*' and (pattern[j - 1] == '.' or pattern[j - 1] == str[i - 1]):
dp[i][j] = dp[i - 1][j - 1]
#当前的字符为*
elif j >= 2 and pattern[j - 1] == '*':
#若是前一位为.或者前一位可以与这个数字匹配
if pattern[j - 2] == '.' or pattern[j - 2] == str[i - 1]:
#转移情况
dp[i][j] = dp[i - 1][j] or dp[i][j - 2]
else:
#不匹配
dp[i][j] = dp[i][j - 2]
return dp[n1][n2]
复杂度分析:
- 时间复杂度:,其中和分别为字符串和模版串的长度,初始化遍历矩阵一边,状态转移遍历整个dp矩阵
- 空间复杂度:,动态规划辅助数组dp的空间