【每日刷题】Day162
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 3302. 字典序最小的合法序列 - 力扣（LeetCode）
1. 3302. 字典序最小的合法序列 - 力扣（LeetCode）
//思路：前后缀和+贪心
//本题要点在于：如何贪？
//根据题目可知，我们 最多只能改变一个字符 使得 word1中的字典序最小的序列对应的字符串 与 word2 完全相等
//既然如此，我们首先肯定是优先考虑：word1 中 字典序最小的、不需要改变字符 就能和 word2 完全相同的字符串
//其次考虑：改变一个字符后，这个字符所在的序列对应的字典序是最小的 并且 对应的字符串和 word2 完全相同。想要找出这个序列，就必须借助前、后缀。
//前缀：word1的当前字符之前有多少个字符和 word2 按照顺序匹配
//后缀：word1的当前字符之后有多少个字符和 word2 按照顺序匹配
class Solution {
public:
vector<int> validSequence(string word1, string word2)
{
int n = word1.size(),m = word2.size();
vector<int> post(n+1);
vector<int> ans(m);
for(int i = n-1,j = m-1;i>=0;i--)//计算后缀
{
if(j>=0&&word1[i]==word2[j]) j--;
post[i] = m-j-1;
}
int p = 0;//前缀:word1 和 word2 前面匹配的长度
for(int i = 0,j = 0;i<n;i++)
{
if(j<m&&word1[i]==word2[j])//优先考虑不需要改变字符就相等的字符串
{
ans[p++] = i;
if(++j==m) return ans;
continue;
}
if(p+post[i+1]+1>=m)//如果遇到不相等的需要改变，判断是否应该改变当前字符来形成序列。判断条件：前、后缀和 + 1的长度 ≥ m
{
ans[p++] = i++;
while(p<m&&i<n)//当改变了一个字符后，就只能继续去后面找匹配的，相同的字符，无法再进行改变操作
{
if(word1[i]==word2[p]) ans[p++] = i;
i++;
}
return ans;
}
}
return {};
}
};
2. 44. 通配符匹配 - 力扣（LeetCode）
//思路：动态规划——二维dp
class Solution {
public:
bool isMatch(string s, string p)
{
int n = s.size(),m = p.size();
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
dp[0][0] = true;
for(int j = 0;j<m;j++)//考虑 s 字符串为空的情况
{
if(p[j]!='*') break;
dp[0][j+1] = true;
}
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)//套用状态转移方程
{
if(p[j]=='*') dp[i+1][j+1] = dp[i][j+1]||dp[i+1][j];
else if(p[j] == s[i] || p[j] == '?') dp[i+1][j+1] = dp[i][j];
}
}
return dp[n][m];
}
};
3. 10. 正则表达式匹配 - 力扣（LeetCode）
//思路：动态规划——二维dp
//大体思路与上一题类似，区别在于 '*' 的判断
class Solution {
public:
bool isMatch(string s, string p)
{
int n = s.size(),m = p.size();
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
s = ' '+s,p = ' '+p;
dp[0][0] = true;
for(int j = 2;j<=m;j+=2)
{
if(p[j]=='*') dp[0][j] = true;//处理 s 为空串的情况
else break;
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
if(p[j]=='*')//套用状态转移方程，这里进行了合并处理
dp[i][j] = dp[i][j-2] ||(p[j-1]=='.'||p[j-1]==s[i])&&dp[i-1][j];
else
dp[i][j] = (p[j]=='.'||p[j]==s[i])&&dp[i-1][j-1];
}
}
return dp[n][m];
}
};