囧问：好像aa的点数合并us airway后莫名奇妙的少了好几万。# Money - 海外理财
p*3
1 楼
//DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
}
else i += 1;
}
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2;)
{
if (pattern[j] != '*' && pattern[j] != '+')
{
DP[i][j] = (((str[i-1] == pattern[j-1]) || pattern[j-1] == '
.') && DP[i-1][j-1]);
j++;
}
else
{
int iter = i;
if (pattern[j] == '+')
{
if (pattern[j-1] != '.' && pattern[j-1] != str[i-1])
{
j += 2;
continue;
}
else iter--;
}
do
{
if (DP[iter][j-1])
{
DP[i][j] = true;
DP[i][j+1] = true;
break;
}
}
while (iter > 0 && str[iter-- - 1] == pattern[j-1]);
j += 2;
}
}
}
return DP[len1][len2];
}
============================
以前一直觉得很难，发现也不是太难写
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
}
else i += 1;
}
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2;)
{
if (pattern[j] != '*' && pattern[j] != '+')
{
DP[i][j] = (((str[i-1] == pattern[j-1]) || pattern[j-1] == '
.') && DP[i-1][j-1]);
j++;
}
else
{
int iter = i;
if (pattern[j] == '+')
{
if (pattern[j-1] != '.' && pattern[j-1] != str[i-1])
{
j += 2;
continue;
}
else iter--;
}
do
{
if (DP[iter][j-1])
{
DP[i][j] = true;
DP[i][j+1] = true;
break;
}
}
while (iter > 0 && str[iter-- - 1] == pattern[j-1]);
j += 2;
}
}
}
return DP[len1][len2];
}
============================
以前一直觉得很难，发现也不是太难写
