H
H
Homemade2021-12-10 18:04:52
C++ / C#
Homemade, 2021-12-10 18:04:52

Why is the solution to the problem wrong?

The task is here .
My decision :

spoiler
#include <iostream>
#include <string>
 
using namespace std;
 
bool is_subsequence(string s, string t)
{
    char tmp;
    bool is_sub = true;
    for (int i = 0; s.size(); i++) {
        tmp = s[0];
        if (t.find_first_of(tmp, i) == string::npos) {
            is_sub = false;
        }
        s.erase(0, 1);
    }
 
    if (is_sub)
        return true;
    else
        return false;
}
 
int f(string str, char c)
{
    int ans = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i]==c) {
            ans++;
        }
    }
    return ans;
}
 
int main()
{
    int tt;
    cin >> tt;
    while (tt--) {
        string s, t, p;
        cin >> s >> t >> p;
 
        if (!is_subsequence(s, t)) {
            cout << "NO" << endl;
            continue;
        }
 
        bool b = true;
        for (int i = 0; i < t.size(); i++) {
            if (f(t, t[i]) > f(s, t[i]) + f(p, t[i])) {
                b = false;
            }
        }
 
        if (b) {
            cout << "YES" << endl;
        }
        else
            cout << "NO" << endl;
    }
    
    return 0;

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2021-12-10
@Homemade

is_subsequence is misspelled. What is your algorithm? Why do you think it should work?
For example, it does not work on the test s="abc" t="zzzzzcba". Your implementation will say that abc is a subsequence, when in fact it is not.
I also want to separately draw attention to the genius of the code:

if (is_sub)
        return true;
    else
        return false;

He seems a bit over-the-top to me.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question