C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-03-05
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string str, string pattern) {
// write code here
//simplify the pattern
// char compar
return partMatch(str,pattern, 0,str.length(), 0, pattern.length());
}
bool partMatch(string str, string pattern,int str_index,int str_size,int pattern_index,int pattern_size){
//return situation
if(str_index==str_size){
if(pattern_index==pattern_size) return true;
if(pattern_index==pattern_size-2&&pattern[pattern_index+1]=='*') return true;
return false;
}
if(pattern_index==pattern_size) return false;
//char+char/. no *
if(str[str_index]==pattern[pattern_index]||pattern[pattern_index]=='.'){
if(pattern_index<pattern_size-1&&pattern[pattern_index+1]=='*'){
//find the last same *
int offset=0;
while(pattern_index+1+offset<pattern_size-1&&pattern[pattern_index+1+offset]=='*'&&pattern[pattern_index+offset]==pattern[pattern_index]){
offset+=2;
}
offset-=2;
return partMatch(str,pattern,str_index+1,str.length(), pattern_index+offset, pattern.length())||partMatch(str,pattern,str_index+1,str.length(), pattern_index+offset+2, pattern.length())||partMatch(str,pattern,str_index,str.length(), pattern_index+offset+2, pattern.length());
}
return partMatch(str,pattern,str_index+1,str.length(), pattern_index+1, pattern.length());
}
else{
if(pattern_index<pattern_size-2&&pattern[pattern_index+1]=='*') return partMatch(str,pattern,str_index,str.length(), pattern_index+2, pattern.length());
return false;
}
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-05-31
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string str, string pattern) {
int n1 = str.length();
int n2 = pattern.length();
// dp[i][j]表示str[0:i]与pattern[0:j]是否匹配
vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
// 边界初始化
dp[0][0] = true; // 空串匹配
// 初始化第一行
for (int i=2; i<=n2; i++){
// 遇到*
if (pattern[i-1] == '*')
dp[0][i] = dp[0][i-2];
}
for (int i=1; i<=n1; i++){
for(int j=1; j<=n2; j++){
// 当遇到的字符不为*，判断是否匹配
if(pattern[j-1] != '*' && (pattern[j-1] == str[i-1] || pattern[j-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][j-2] || dp[i-1][j];
else
dp[i][j] = dp[i][j-2];
}
}
}
return dp[n1][n2];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-03-12
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int j = 2; j <= n; j++) {
if (p[j - 1] == '*')
dp[0][j] = dp[0][j - 2];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
else if (p[j - 1] == '*') {
if (j > 1) {
if (dp[i][j - 2]) dp[i][j] = true;
else if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
dp[i][j] = dp[i - 1][j];
}
}
}
}
}
return dp[m][n];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-03-11
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string str, string pattern) {
// write code here
//dp
if(pattern.empty()) return str.empty();
int m = str.size(), n = pattern.size();
bool dp[m + 1][n + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 2; i <= n; i++)
{
if(pattern[i - 1] == '*')
dp[0][i] = dp[0][i - 2];
}
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
{
dp[i][j] = dp[i - 1][j - 1];
}
else if(pattern[j - 1] == '*')
{
if(dp[i][j - 1])//*匹配一次
{
dp[i][j] = dp[i][j - 1];
}
else if(j >= 2 && dp[i][j - 2])//*匹配0次
{
dp[i][j] = dp[i][j - 2];
}
else if(i >= 2 && j >= 2)//可能匹配2次及以上
{
dp[i][j] = dp[i - 1][j] && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.');
}
}
}
}
return dp[m][n];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-02-28
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string str, string pattern) {
// write code here
vector<vector<bool>> dp(str.length()+1, vector<bool>(pattern.length()+1));
dp[0][0] = true;
for(int i=1; i<str.length()+1; i++){
dp[i][0] = false;
}
for(int j=1; j<pattern.length()+1; j++){
dp[0][j] = pattern[j-1]=='*' && dp[0][j-2];
for(int i=1; i<str.length()+1; i++){
if(pattern[j-1]!='*'){
dp[i][j] = (pattern[j-1]==str[i-1] || pattern[j-1]=='.') && dp[i-1][j-1];
}else{
dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (pattern[j-2]==str[i-1] || pattern[j-2]=='.'));
}
}
}
return dp[str.length()][pattern.length()];
}
};
