Double sequence DP
44. Wildcard Matching
3 min readJul 6, 2020
//without optimization
class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length(), n = p.length();
s = "#" + s;
p = "#" + p;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][0] = 1;
//dp[0][x]
for(int j=1;j<=n;++j)
{
if(p[j]=='*')dp[0][j] = dp[0][j-1];
}
//dp[x][0], no needed to update.
for (int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if (p[j]=='?')
{
dp[i][j] = dp[i-1][j-1];
}
else if (p[j] == '*')
{
for (int k=0;k<=i;++k)
{
dp[i][j] |= dp[i-k][j-1];
}
}
else if(p[j]==s[i])dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
};Improved version
class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length(), n = p.length();
s = "#" + s;
p = "#" + p;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][0] = 1;
//dp[0][x]
for(int j=1;j<=n;++j)
{
if(p[j]=='*')dp[0][j] = dp[0][j-1];
}
//dp[x][0], no needed to update.
for (int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if (p[j]=='?')
{
dp[i][j] = dp[i-1][j-1];
}
else if (p[j] == '*')
{
dp[i][j] = dp[i][j-1] || dp[i-1][j];
}
else if(p[j]==s[i])dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
};321. Create Maximum Number
The video explanation can be found HERE.
Put everything inside the loops (TLE)
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
nums1.insert(nums1.begin(), 0);
nums2.insert(nums2.begin(), 0);
string dp[m+1][n+1][K+1];
for (int i=0;i<=m;++i)
for (int j=0;j<=n;++j)
for (int k=1;k<=min(i+j, K);++k)
{
dp[i][j][k] = "";
if(i>0)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+to_string(nums1[i]));
if(j>0)dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+to_string(nums2[j]));
if(i>0)dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
if(j>0)dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);}
vector<int> ret;
for (auto c:dp[m][n][K])
{
ret.push_back(c-'0');
}
return ret;
}
};
双序列dp的逻辑好tricky。如果把边界值放外边的话，也还是需要四次判断语句。主要是为了涵盖所有的情况。
- 包含i，
- 不包含i，
- 包含j，
- 不包含j。
如果改为三个条件，在这个测试用例会出错
[5,2,2][6,4,1]3
具体错误点在这个case下面
[5， 2]
[6] 如果按照三个条件，则最大值为 max（62， 56） = 62. 正确值应该为65. 这个例子下，所有的情况为：
52， 62， 56， 26， 65.
- 结尾为2的情况为： 52， 62,
- 结尾不为2的情况为： 56, 26 ，65
- 结尾为6的情况为： 56， 26
- 结尾不为6 的情况为：52,62, 65
如上所有情况有重叠，但是不会漏掉任何情况。我们最终可以把其合并为
- 结尾为2的情况，
- 结尾不为2的情况（包含结尾为6的情况， 及单独去除2不用的情况）
- 结尾为6的情况，
- 结尾不为6的情况（包含结尾为2的情况，及单独去除6不用的情况） —
— 》
- 结尾为2的情况
- 单独去除2不用的情况
- 结尾为6的情况
- 单独去除6不用的情况
所以最后为四种情况, as shown in the code.
Put everything outside of the loop(TLE)
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
nums1.insert(nums1.begin(), 0);
nums2.insert(nums2.begin(), 0);
string dp[m+1][n+1][K+1];
for (int j=1;j<=n;++j)
for(int k=1;k<=min(j, K);++k)
{
dp[0][j][k] = max(dp[0][j-1][k], dp[0][j-1][k-1]+to_string(nums2[j]));
}
for (int i=1;i<=m;++i)
for(int k=1;k<=min(i, K);++k)
{
dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][0][k-1]+to_string(nums1[i]));
}
for (int i=1;i<=m;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=min(i+j, K);++k)
{
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1]+to_string(nums1[i]));
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+to_string(nums2[j]));
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
//dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]);
}
vector<int> ret;
for (auto c:dp[m][n][K])
ret.push_back(c-'0');
return ret;
}
};An AC solution
class Solution {
public:
deque<int> get_max(vector<int>& nums, int k){
int remain = nums.size() - k;
deque<int> ret;
for (int i=0; i<nums.size();++i)
{
while(remain && ret.size()>0 && nums[i]>ret.back())
{
remain--;
ret.pop_back();
}
ret.push_back(nums[i]);
}
ret.resize(k);
return ret;
}
vector<int> merge(deque<int> p1, deque<int> p2){
const int K = p1.size() + p2.size();
vector<int> ret;
for(int i=0;i<K;++i)
{
if(p2>p1)
{
ret.push_back(p2.front());
p2.pop_front();
}
else
{
ret.push_back(p1.front());
p1.pop_front();
}
}
return ret;
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int K) {
const int m = nums1.size(), n = nums2.size();
vector<int> ret;
for (int i=0;i<=K;++i)
{
if (i>m) break;
if (K-i>n) continue;
deque<int> p1 = get_max(nums1, i);
deque<int> p2 = get_max(nums2, K-i);
vector<int> temp = merge(p1, p2);
ret = max(ret, temp);
}
return ret;
}
};