使用DP的缩略语问题中的错误答案
使用DP的缩略语问题中的错误答案
提问于 2020-11-30 08:45:41
有人能解释一下我的代码出了什么问题吗？我在7个测试用例中被“中止调用”。休息是成功的。
我有一个大小为2dDP的数组: n+1 x，m+1为n，m分别为a和b的大小。因此，行表示字符串a，列表示字符串b。
首先，我将dp设置为1，因为可以将空字符串转换为空字符串。
因此，最初，我检查是否可以将a的任何子字符串转换为空字符串(在第一个for-循环中)。这对于没有大写字母的a的所有子字符串都是正确的。一旦有大写字母，其余的子字符串就无法转换。
然后(在下一个双循环中)，我正在检查所有的案例.
Case 1：ai-1 == bi-1 ->如果两个字母完全相同，那么dpi = dpi-1
案例2：ai-1是小写(这有2个子案例)：
案例2.1：ai-1和bj-1是同一个字母(但不是同一个字母) ->，那么我们可以更改ai-1或删除它。那么: dpi = dpi-1 \ dpi-1。
案例2.2：在这种情况下，ai-1和bj-1不是相同的->，我们只能删除ai-1，因为它是小写的。So: dpi = dpi-1
程序的主要逻辑就在缩写()函数中。
代码(编辑)：
#include <bits/stdc++.h>
using namespace std;
bool isSame(const char &a, const char &b)
{
return a == b || abs(a - b) == 32;
}
bool isLower(const char &a)
{
return a > 90 && a < 123;
}
// Complete the abbreviation function below.
string abbreviation(const string &a, const string &b)
{
int n = a.size(), m = b.size();
if (m > n)
return "NO";
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
if (isLower(a[i - 1]) && dp[i - 1][0])
dp[i][0] = 1;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= i; ++j)
{
if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1];
if (isLower(a[i - 1]))
{
if (isSame(a[i - 1], b[j - 1]))
dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j];
else if (dp[i - 1][j])
{
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[n][m] ? "YES" : "NO";
}
int main()
{
int t;
cin >> t;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
while (t--)
{
string a, b;
getline(cin, a);
getline(cin, b);
cout << abbreviation(a, b) << "\n";
}
return 0;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2020-11-30 09:33:39
代码中的错误是“分段错误”。
因为有以下循环：
for (int j = 1; j <= i; ++j)由于循环正在迭代，直到i(可以大于m，即b的大小)。这就是分段错误的原因。
下面的代码通过了所有的测试用例。
#include <bits/stdc++.h>
using namespace std;
bool isSame(const char&a, const char&b){
return a==b || abs(a-b)==32;
}
bool isLower(const char&a){
return a >90 && a<123;
}
// Complete the abbreviation function below.
string abbreviation(string a, string b) {
int n = a.size(), m = b.size();
if(m>n)
return "NO";
int dp[n+1][m+1] = {};
dp[0][0] = 1;
for(int i=1; i<=n; ++i)
if(isLower(a[i-1]) && dp[i-1][0])
dp[i][0] = 1;
for(int i=1; i<=n; ++i)
for(int j =1; j<=min(i,m); ++j){
if(a[i-1]==b[j-1])
dp[i][j] = dp[i-1][j-1];
if(isLower(a[i-1]))
{
if(isSame(a[i-1], b[j-1]))
dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
else if(dp[i-1][j])
dp[i][j] = dp[i-1][j];
}
}
return dp[n][m] ? "YES" : "NO";
}
int main()
{
int q;
cin >> q;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
for (int q_itr = 0; q_itr < q; q_itr++) {
string a;
getline(cin, a);
string b;
getline(cin, b);
string result = abbreviation(a, b);
cout << result << "\n";
}
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65070389
复制相关文章
相似问题
腾讯云开发者
