I was solving a problem on Geeksforgeeks for finding the largest word in the dictionary. I wrote the code accordingly but stuck in between as the flow is not entering inside if statement of inner 2nd for loop inside the main function.
#include <iostream>
using namespace std;
int lcs(string s,string target)
{
int m = s.size(),n = target.size();
int dp[m+1][n+1];
for(int i = 0;i<=m;i++)
{
for(int j =0;j<=n;j++)
{
if(i ==0 || j ==0)
dp[i][j] = 0;
else if(s[i] == target[j])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
int main() {
//code
int t,n,loc=0,MaX = -999;
cin>>t;
for(int i= 0;i < t;i++)
{
cin>>n;
string s[n];
for(int j = 0;j<n;j++)
{
cin>>s[j];
}
string target;
cin>>target;
for(int j = 0;j<n;j++)
{
int Lcs = lcs(s[j],target);
cout<<"s["<<j<<"] s[j] size-> "<<s[j].size()<<" lcs size -> "<<Lcs<<" MaX value->"<<MaX<<"\n";
// It is not entering inside this if condition
if((s[j].size() > MaX) && (s[j].size() == Lcs))
{
cout<<"enter inside loop\n";
MaX = s[j].size();
loc = j;
}
}
cout<<s[loc]<<"\n";
}
return 0;
}
For Input:
2
4
ale apple monkey plea
abpcplea
4
pintu geeksfor geeksgeeks forgeek
geeksforgeeks
The OUTPUT flow is like this
s[0] s[j] size-> 3 lcs size -> 3 MaX value->-999
s[1] s[j] size-> 5 lcs size -> 5 MaX value->-999
s[2] s[j] size-> 6 lcs size -> 2 MaX value->-999
s[3] s[j] size-> 4 lcs size -> 4 MaX value->-999
ale
s[0] s[j] size-> 5 lcs size -> 1 MaX value->-999
s[1] s[j] size-> 8 lcs size -> 8 MaX value->-999
s[2] s[j] size-> 10 lcs size -> 10 MaX value->-999
s[3] s[j] size-> 7 lcs size -> 7 MaX value->-999
pintu
Expected OUTPUT
apple
geeksgeeks
Aucun commentaire:
Enregistrer un commentaire