# Daily HackerRank Challenge - Day 24

Daily HackerRank Challenge (30 Part Series)

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.

# Abbreviation Sample Input

1
daBcd
ABC


Sample Output

YES


Using a simple DP approach can resolve this problem. Let's say we have dp[i,j], we set it to 1 if there is a way to transform the first i characters of A into the first j characters of B. If it is not possible to do that, set it to 0. If dp[asz][bsz] is 1, return YES, else return NO. We just need to figure out which states can be achievable.

// AbCdE
// AFE
//     A F E
//   1 0 0 0
// A 0 1 0 0
// b 1 1 0 0
// C 0 0 0 0
// d 1 0 0 0
// E 0 0 0 0


Final Solution

string abbreviation(string a, string b) {
int asz = (int)a.size();
int bsz = (int)b.size();
int dp[asz+1][bsz+1];
memset(dp,0,sizeof(int)*(asz+1)*(bsz+1));
dp = 1;
for(int i=1;i<=asz;i++) {
if(!isupper(a[i-1])) dp[i]=1;
}
for(int i=1;i<=asz;i++){
for(int j=1;j<=bsz;j++){
if(a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1];
else if(isupper(a[i-1])) dp[i][j] = 0;
else if(toupper(a[i-1])==b[j-1]) dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
else dp[i][j] = max(dp[i-1][j],dp[i-1][j]);
}
}
return dp[asz][bsz]?"YES":"NO";
}


# Complete Code

Check out the complete code via below link

Daily HackerRank Challenge (30 Part Series)

### Discussion   