关键词:动态规划
这题确认dp状态不难,最关键也是最麻烦的是找到正确的转移方程。我参考了这位大神的答案。
dp[i][j]
?:代表字符串?s
?的前?i
?个字符和?p
?的前?j
?个字符能否匹配。(注意这里dp的第0行和第0列表示s为空和p为空的情况)
dp[0][0]=1 因为空字符串和空字符串可以匹配
如下表格所示
‘’ | . | * | a | |
‘’ | 1 | 0 | 0 | 0 |
b | 0 | 0 | 0 | 0 |
c | 0 | 0 | 0 | 0 |
a | 0 | 0 | 0 | 0 |
假如我们需要确认dp[i][j]的情况。
需要分成两种大的情况:
????????(即p字符串当前检测的字符,-1是因为dp方程里面我们多开了一行)
????????那么就看p[j-1]是否等于s[i-1] 或?p[j-1]是否等于'.':如果是,则dp[i][j]和dp[i-1][j-1]状态一致(多加了一组匹配字符);如果不是,则保持0。
????????比如:
????????p[j-1]等于'.':dp[i][j]和dp[i-1][j-1]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 0 | 0 |
c | 0 | 0 | 0 | 0 |
a | 0 | 0 | 0 | 0 |
?????????p[j-1]等于'.':dp[i][j]和dp[i-1][j-1]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 0 | 0 |
a | 0 | 0 | 0 | 0 |
?????????p[j-1]等于s[i-1]:dp[i][j]和dp[i-1][j-1]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 1 | 0 |
a | 0 | 0 | 1 | 1 |
这一步的具体代码:
if (i > 0 && j > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))//不是*
{
dp[i][j] = dp[i - 1][j - 1];
}
? ? ? ? 这个时候需要把*和前面的字符c看作一个整体,一起讨论,因为*的内容得取决于c。
? ? ? ? 那么还得分两种情况,这两种情况得取 或:
????????????????这个时候得看p[j-2]是否等于s[i-1] 或?p[j-2]是否等于'.':如果是,则dp[i][j]和dp[i-1][j]状态一致(相当于s后移,p不用动,因为*可以充当多个c);如果不是,则保持0。
? ? ? ? ? ? ? ? 比如:
????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 0 | 0 |
a | 0 | 0 | 0 | 0 |
????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 1 | 0 |
a | 0 | 0 | 0 | 0 |
????????????????p[j-2]等于'.':dp[i][j]和dp[i-1][j]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 1 | 0 |
a | 0 | 0 | 1 | 0 |
????????????????这个时候就得看??这一对c*的前面的那个字符p[j-3]了,它对应的状态是dp[i][j-2]。因此,这个时候dp[i][j]和dp[i][j-2]状态一致。
? ? ? ? ? ? ? ? 比如:
????????????????不看c*:dp[i][j]和dp[i][j-2]状态一致
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 0 | 0 | 0 |
c | 0 | 0 | 0 | 0 |
a | 0 | 0 | 0 | 0 |
?
?这一步的具体代码:
if (j > 1 && p[j - 1] == '*')//是*
{
dp[i][j] = dp[i][j] || dp[i][j - 2];//不看c*
if (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))//看c*
dp[i][j] = dp[i][j] || dp[i - 1][j];//注意这里是dp[i - 1][j]不是dp[i][j - 1]
}
????????取dp[s.size()][p.size()]
‘’ | . | * | a | |
‘’ | 1 | 0 | 1 | 0 |
b | 0 | 1 | 1 | 0 |
c | 0 | 0 | 1 | 0 |
a | 0 | 0 | 1 | 1 |
时间复杂度O(nm)
空间复杂度O(nm)
class Solution {
public:
bool articleMatch(std::string s, std::string p) {
std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(p.size() + 1));
dp[0][0] = 1;
for (int i = 0; i < s.size() + 1; ++i)
{
for (int j = 0; j < p.size() + 1; ++j)
{
if (j > 1 && p[j - 1] == '*')//是*
{
dp[i][j] = dp[i][j] || dp[i][j - 2];//不看c*
if (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))//看c*
dp[i][j] = dp[i][j] || dp[i - 1][j];//注意这里是dp[i - 1][j]不是dp[i][j - 1]
}
else if (i > 0 && j > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))//不是*
{
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[s.size()][p.size()];
}
};