Buonasera stavo provando a risolvere il problema ois_jumps e penso di aver trovato la soluzione ma il codice continua a fare 10/100, credo il problema sia la funzione jump e in particolare il secondo punto dove controlla se è possibile sostituire un solo carattere per far combaciare le stringhe.
• w2 is obtained from w1 by deleting one letter.
• w2 is obtained from w1 by replacing one of the letters in w1 by some letter that appears to its right in w1 and which is also to its right in alphabetical
order
Da quanto ho capito date due stringhe A e B di uguale dimensione posso sostituire A[i] con B[i] solo se B[i] è presente in A ad un indice ind > i giusto??
Ecco il mio codice, grazie in anticipo per l’aiuto:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100
bool findLast(string a, char b, int ind)
{
for (int i = a.size() - 1; i > ind; i--)
if (a[i] == b) return true;
return false;
}
bool jump(string a, string b)
{
if (a.size() == b.size() + 1)
{
for (int i = 0; i < a.size(); i++)
{
string temp = a.substr(0, i) + a.substr(i + 1);
if (temp == b) return true;
}
}
else if (a.size() == b.size())
{
int count = 0;
for (int i = 0; i < a.size(); i++)
{
if (a[i] < b[i] && findLast(a, b[i], i)) count++;
else if (a[i] > b[i]) return false;
}
return count <= 1;
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int N;
cin >> N;
string W[MAXN];
for (int i = 0; i < N; i++)
cin >> W[i];
sort(W, W + N, [](string a, string b) {
if (a.size() == b.size()) return a < b;
return a.size() > b.size();
});
int dp[MAXN];
fill(dp, dp + N, 1);
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (jump(W[j], W[i]) && dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
cout << *max_element(dp, dp + N);
}```