In this HackerRank Abbreviation Interview preparation kit problem you need to complete the function abbreviation.


HackerRank Abbreviation Interview preparation kit solution


Problem solution in Python programming.

import sys

q = int(input().strip())
for i in range(q):
    a = input().strip()
    b = input().strip()
    #store all possibilities
    bpos = {}
    for i in range(len(b)):
        bpos[b[i]] = (bpos[b[i]] | set([i])) if b[i] in bpos else set([i])
    possibilities = set([0])
    for i in range(len(a)):
        if a[i].upper() in bpos:
            intersection = bpos[a[i].upper()] & possibilities
            advancement = set([i + 1 for i in intersection])
        else:
            advancement = set([])
        if a[i].upper() == a[i]:#capitals must follow the intersection
            possibilities = advancement
        else:
            possibilities = possibilities | advancement
    print("YES" if (len(b)) in possibilities else "NO")




Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the abbreviation function below.
    static String abbreviation(String a, String b) {
        boolean[][] isValid = new boolean[a.length()+1][b.length()+1];
        isValid[0][0] = true;

        for (int i= 1; i <= a.length(); i++) {
            if (Character.isUpperCase(a.charAt(i - 1))) {
                isValid[i][0] = false;
            }
            else isValid[i][0] = true;
        }
        // tabulation from start of string
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i-1) == b.charAt(j-1)) {
                    isValid[i][j] = isValid[i-1][j-1];
                }else if (Character.toUpperCase(a.charAt(i-1))  ==  b.charAt(j-1)) {
                    isValid[i][j] = isValid[i-1][j-1] || isValid[i-1][j];
                }else if (Character.isUpperCase(a.charAt(i-1))) {
                    isValid[i][j] = false;
                }else {
                    isValid[i][j] = isValid[i-1][j];
                }
            }
        }
        return isValid[a.length()][b.length()]? "YES" : "NO";


    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String a = scanner.nextLine();

            String b = scanner.nextLine();

            String result = abbreviation(a, b);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}


Problem solution in C++ programming.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <unordered_set>
using namespace std;

char A[2000], B[2000];
int Q, n, m;
bool ok[1100][1100];

int main() {
	scanf("%d", &Q);
	while (Q--) {
		scanf("%s%s", A + 1, B + 1);
		n = strlen(A + 1);
		m = strlen(B + 1);
		memset(ok, false, sizeof ok);
		ok[0][0] = true;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
	if (ok[i][j]) {
		if ('a' <= A[i + 1] && A[i + 1] <= 'z')
			ok[i + 1][j] = true;
			if (A[i + 1] == B[j + 1])
			ok[i + 1][j + 1] = true;
	if ('a' <= A[i + 1] && A[i + 1] <= 'z' && A[i + 1] - 'a' + 'A' == B[j + 1])
			ok[i + 1][j + 1] = true;
				}
		if (ok[n][m])
			printf("YES\n");
		else
			printf("NO\n");
	}
}


Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>

int main() {
    char a[1000];
    char b[1000];
    int q,n;
    scanf("%d",&q);
    for (int i = 0; i < q; i++) {
        scanf("%s",a);
        scanf("%s",b);

        int curr = 0;
        n = strlen(a);
        for (int j = 0; j < n; j++) {
            //if (b[curr] == toupper(a[j]) || b[curr] == a[j]) {
            if (b[curr] == a[j]) {  
                curr++;
            }
            else {
                if (isupper(a[j])) {
                    curr = 0;
                    break;
                }
            }
        }
        if (curr == strlen(b)) {
            printf("YES\n");
        }
        else {
            for (int j = 0; j < n; j++) {
                if (b[curr] == toupper(a[j]) || b[curr] == a[j]) {
                //if (b[curr] == a[j]) {  
                    curr++;
                }
                else {
                    if (isupper(a[j])) {
                        curr = 0;
                        break;
                    }
                }
            }
            if (curr == strlen(b)) {
                printf("YES\n");
            }
            else 
                printf("NO\n");
        }
    }
    
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}


Problem solution in JavaScript programming.

function processData(input) {
    var lines = input.split("\n");

    function readLine(){
        var n = 0;
        this.nxLn = function(){
            return n++;
        }
    }

    var rd = new readLine();

    var q = parseInt(lines[rd.nxLn()]);

    var isLowerCase = function(value){
        if(value.charCodeAt(0)>96){
            return true;
        } else {
            return false;	
        }
    }

    var containsUpperCase = function(value){
        for(var i=0;i<value.length;i++){
            if(!isLowerCase(value.substr(i,1))){
                return true;
            }
        }
        return false;
    }

    while (q!==0) {
        var a = lines[rd.nxLn()];
        var b = lines[rd.nxLn()];

        var firstCondition = true;

        b.split("").forEach(val=>{
            var ind = a.indexOf(val);
            if(ind==-1){
                ind = a.indexOf(val.toLowerCase());
            }
            if(ind==-1){
                firstCondition = false;
            }
            if(containsUpperCase(a.substr(0,ind))){
                firstCondition = false;
            }
            a = a.substr(ind+1);
        });

        if(containsUpperCase(a)){
            firstCondition = false;
        }

        if(firstCondition){
            console.log("YES");
        } else {
            console.log("NO");
        }

        q--;
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});