loading...

Daily HackerRank Challenge - Day 24

wingkwong profile image Wing-Kam ・2 min read

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

About

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


Abbreviation

image

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[0][0] = 1;
    for(int i=1;i<=asz;i++) {
        if(!isupper(a[i-1])) dp[i][0]=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)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide