In this post, we will solve HackerRank Abbreviation Problem Solution.
You can perform the following operations on the string, a:
- Capitalize zero or more of a’s lowercase letters.
- Delete all of the remaining lowercase letters in a.
Given two strings, a and b, determine if it’s possible to make a equal to b as described. If so, print YES on a new line. Otherwise, print NO.
For example, given a = AbcDE and b = ABDE, in a we can convert b and delete c to match b. If a = AbcDE and b = AFDE. matching is not possible because letters may only be capitalized or discarded, not changed.
Function Description
Complete the function abbreviation in the editor below. It must return either YES or
NO.
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 q, the number of queries.
Each of the next & pairs of lines is as follows:
- The first line of each query contains a single string, a.
-The second line of each query contains a single string, b.
Output Format
For each query, print YES on a new line if it’s possible to make string a equal to string b. Otherwise, print NO.
Sample Input
1
daBcd
ABC
Sample Output
YES
Abbreviation C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int f(char *a,char *b,int starta,int startb){
if(b[startb]=='\0'){
for(int i=starta;i<strlen(a);i++){
if(a[i]>='A'&&a[i]<='Z')
return 0;
}
return 1;
}
else{
for(int i=starta;i<strlen(a);i++){
int x=0;
if((a[i]>='A'&&a[i]<='Z')&&(a[i]!=b[startb]))
return 0;
else if (b[startb]==((a[i]>='A'&&a[i]<='Z'?a[i]:a[i]-32))){
x=f(a,b,i+1,startb+1);
if(x)
return 1;
}
}
return 0;
}
}
int main() {
int t=0;
scanf("%d",&t);
for(int i=0;i<t;i++){
char a[1001];
char b[1001];
scanf("%s",a);
scanf("%s",b);
a[strlen(a)]='\0';
b[strlen(b)]='\0';
if(strlen(b)>strlen(a))
printf("NO\n");
else if(strlen(a)==strlen(b)){
if(strcmp(a,b)==0)
{printf("YES\n");continue;}
else
{ printf("NO\n");continue;}
}
if(f(a,b,0,0))
printf("YES\n");
else{
printf("NO\n");
}
}
return 0;
}Abbreviation C++ Solution
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
using namespace std;
char upper(char x){
if(x>='a'&&x<='z')
return (char)(x-'a'+'A');
return x;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin>>q;
while(q--){
string a,b;
cin>>a>>b;
int low[1005];
memset(low,0,sizeof low);
int j=0;
bool ok=1;
for(int i=0;i<a.size();++i){
if(j<=b.size()&&upper(a[i])==b[j]){
if(upper(a[i])!=a[i])
low[j]=1;
else
low[j]=0;
++j;
}
else if(a[i]>='A'&&a[i]<='Z'){
--j;
while(b[j]!=a[i]&&j>=0&&low[j]==1)
--j;
if(j<0||(low[j]==0)){
ok=0;
break;
}
low[j]=0;
++j;
}
}
if(j==b.size()&&ok)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
Abbreviation C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine());
while (t-- > 0)
{
char[] A = Console.ReadLine().ToCharArray();
char[] B = Console.ReadLine().ToCharArray();
int n = A.Length;
int m = B.Length;
bool[,] dp = new bool[n, m];
for (int j = 0; j < m; j++)
{
bool upperFlag = false;
for (int i = j; i < n; i++)
{
if (A[i] == B[j] || Char.ToUpper(A[i]) == B[j])
{
if (j == 0) dp[i, j] = true;
if (Char.IsUpper(A[i]))
{
dp[i, j] = dp[i, j] || dp[i - 1, j - 1];
if (dp[i, j])
{
if (upperFlag)
dp[i, j] = false;
else upperFlag = true;
}
}
else dp[i, j] = dp[i, j] || dp[i - 1, j - 1] || dp[i - 1, j];
}
else if (!Char.IsUpper(A[i]) && i > 0)
dp[i, j] = dp[i - 1, j];
}
}
if (dp[n - 1, m - 1]) Console.WriteLine("YES");
else Console.WriteLine("NO");
}
Console.ReadLine();
}
}Abbreviation Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'abbreviation' function below.
*
* The function is expected to return a STRING.
* The function accepts following parameters:
* 1. STRING a
* 2. STRING b
*/
public 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;
}
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";
/* HashMap<Character, Integer> ha = new HashMap<>();
HashMap<Character, Integer> hb = new HashMap<>();
for(char ch: b.toCharArray()){
if(!hb.containsKey(ch)){
hb.put(ch, 1);
}
else{
int f = hb.get(ch);
hb.replace(ch, f+1);
}
}
for(char ch: a.toCharArray()){
// B has uppercase char
if(hb.containsKey(ch)){
if(!ha.containsKey(ch)){
ha.put(ch, 1);
}
// add char while a has less then b
else if(ha.get(ch) < hb.get(ch)){
int f = ha.get(ch);
ha.replace(ch, f+1);
}
// can't remove uppercase char from a
else if (ha.get(ch)+1 > hb.get(ch)) {
return "NO";
}
}
// B has uppercase char
else if(hb.containsKey(Character.toUpperCase(ch))){
ch = Character.toUpperCase(ch);
if(!ha.containsKey(ch)){
ha.put(ch, 1);
}
// add char while a has less then b
else if(ha.get(ch) < hb.get(ch)){
int f = ha.get(ch);
ha.replace(ch, f+1);
}
}
// Not in B and can't be removed
else if(Character.isUpperCase(ch)){
return "NO";
}
// Lower case not in B is not added
}
System.out.println("A " + ha);
System.out.println("B " + hb);
for(Character ch: hb.keySet()){
if(!ha.containsKey(ch)){
return "NO";
}
else if(ha.containsKey(ch)){
if(ha.get(ch) != hb.get(ch)){
return "NO";
}
}
}
return "YES"; */
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, q).forEach(qItr -> {
try {
String a = bufferedReader.readLine();
String b = bufferedReader.readLine();
String result = Result.abbreviation(a, b);
bufferedWriter.write(result);
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}Abbreviation JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the abbreviation function below.
function abbreviation(a, b) {
return trySolve(a, b, 0, 0 ).filter(x => x).length > 0 ? 'YES' : 'NO';
}
function trySolve(a, b){
let queue = [[a.length - 1, b.length - 1]]
let searched = {}
let found = false;
while(queue.length > 0){
let idxes = queue.pop();
let i = idxes[0]
let j = idxes[1]
let outOfA = i == -1;
let finished = outOfA;
if(finished){
found = found || j <= 0;
if(j <= 0) console.log(idxes)
}
if(!a[i]) continue;
let isUpper = a[i].toUpperCase() == a[i]
if(isUpper && a[i].toUpperCase() !== b[j]){
continue;
}
if(j > -1 && a[i] !== undefined && (a[i].toUpperCase() === b[j])){
let key = ((i - 1) + " " + (j - 1))
if(searched[key]){
continue;
}
queue.push([i - 1, j - 1])
searched[key] = true;
}
let isLower = a[i] !== a[i].toUpperCase()
//delete
if(isLower){
let key = (i - 1 + " " + j)
if(searched[key]){
continue;
}
searched[key] = true;
queue.push([i - 1, j])
}
}
return [found]
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const q = parseInt(readLine(), 10);
for (let qItr = 0; qItr < q; qItr++) {
const a = readLine();
const b = readLine();
let result = abbreviation(a, b);
ws.write(result + "\n");
}
ws.end();
}Abbreviation Python Solution
q = int(input())
for i in range(0,q):
a = input()
b = input()
soFar = []
toGo = []
soFar.append([])
toGo.append(list(b))
for j in range(0, len(a)):
c = a[j]
e = len(soFar)
#print("so far")
#print(soFar)
#print("to go")
#print(toGo)
k = 0
while k < e:
if c >= 'a' and c <= 'z':
if len(toGo[k]) > 0 and c.upper() == toGo[k][0]:
ne = soFar[k][:];
ne.append(c.upper())
soFar.append(ne)
toGo.append(toGo[k][1:])
if c >= 'A' and c <= 'Z':
if len(toGo[k]) == 0 or toGo[k][0] != c:
soFar.pop(k)
toGo.pop(k)
k-=1
e-=1
else:
soFar[k].append(c)
toGo[k].pop(0)
k+=1
matched = False
for j in range(0, len(toGo)):
if len(toGo[j]) == 0:
matched = True
if matched:
print("YES")
else:
print("NO")
