ronith
10/13/2018 - 2:20 AM

Abbreviation

You can perform the following operations on the string, :

Capitalize zero or more of 's lowercase letters. Delete all of the remaining lowercase letters in . Given two strings, and , determine if it's possible to make equal to as described. If so, print YES on a new line. Otherwise, print NO.

For example, given and , in we can convert and delete to match . If and , matching is not possible because letters may only be capitalized or discarded, not changed.

Function Description

Complete the function in the editor below. It must return either or .

abbreviation has the following parameter(s):

a: the string to modify b: the string to match Input Format

The first line contains a single integer , the number of queries.

Each of the next pairs of lines is as follows:

  • The first line of each query contains a single string, .
  • The second line of each query contains a single string, .

Constraints

String consists only of uppercase and lowercase English letters, ascii[A-Za-z]. String consists only of uppercase English letters, ascii[A-Z]. Output Format

For each query, print YES on a new line if it's possible to make string equal to string . Otherwise, print NO.

Sample Input

1 daBcd ABC Sample Output

YES Explanation

image

We have daBcd and ABC. We perform the following operation:

Capitalize the letters a and c in so that dABCd. Delete all the remaining lowercase letters in so that ABC. Because we were able to successfully convert to , we print YES on a new line.

Solution: A simple DP approach works. For example, a = "aBbdD" b = "BBD" since the last character in a is upper case and last character in b is also upper case and both are equal, f(a,b) = f("aBbd","BB") Now d can never be made equal to B therfore- f("aBbd","BB") = f("aBb","BB") Now b can be capitalized to B,therfore we have two options - either capitalize b to B or dont capitalize b. f("aBb","BB") = f("aB","B") or f("aB","BB") #Note that this is the 'or' operator. f is a boolean value. if we have something like a = 'C' and b = 'D' then f(a,b) evaluates to False (boolean value). Lastly (for initialization of the dp array)- if a is non-empty and b is empty, then f(a,b) is True only if all the characters in a are lower case. if a is empty and b is non-empty, then f(a,b) is always False. if both are empty then f(a,b) = True

Abbreviation.cpp
content_copyfile_download
//https://www.hackerrank.com/challenges/abbr/problem
#include <bits/stdc++.h>
using namespace std;

bool islower(char c) {
    if (c> 96 && c<123)
        return true;
    return false;
}

string func (string a, string b) {
    int n=a.length(), m= b.length();
    bool dp[n+1][m+1];//check if first j elements of b can be obtained from first i elements of a.
    for (int i=1;i<=m;i++)
        dp[0][i]= 0;//i=0 means length(a)= 0, then b can be obtained from a.
    dp[0][0]=1;
    for (int i=1;i<=n;i++)//if length(b)=0, it means it can be obtained from a, as long as 'a' donot contain uppercase letters.
        dp[i][0]= dp[i-1][0] & islower(a[i-1]);

    for (int i=1;i<=n;i++) {// iterator for no.of elements in a
        for (int j=1;j<=m;j++) { // iterator for no.of elements in b
            if (a[i-1]==b[j-1])//same characters in a and b.
                dp[i][j]= dp[i-1][j-1];
            else if (a[i-1]- 'a'== b[j-1]- 'A')
                dp[i][j]= dp[i-1][j-1] || dp[i-1][j];
            else if (!islower(a[i-1]))// we have encountered an uppercase element in a
                dp[i][j]= 0;
            else
                dp[i][j]= dp[i-1][j];
        }
    }
    return (dp[n][m])?"YES":"NO";
}

int main() {
    int t;
    cin>>t;
    cin>>ws;
    while(t-->0){
        string a,b;
        getline(cin,a);
        getline(cin,b);

        cout<< func(a,b)<<"\n";
    }
}