# Untitled

https://www.hackerrank.com/challenges/abbr/problem
unknown
plain_text
3 years ago
2.5 kB
4
Indexable
Never
```#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

/*
* Complete the 'abbreviation' function below.
*
* The function is expected to return a STRING.
* The function accepts following parameters:
*  1. STRING a
*  2. STRING b
*/

string abbreviation(string a, string b) {
int alen = a.length();
int blen = b.length();
bool dp[alen + 1][blen + 1];
for (int i = 0; i <= alen; i++) {
for (int j = 0; j <= blen; j++) {
dp[i][j] = false;
}
}
dp[0][0] = true; // empty string of 'a' matches with empty string of 'b'
for (int i = 0; i <= alen; i++) {
for (int j = 0; j <= blen; j++) {
if (i > 0) {
if (a[i - 1] >= 'A' && a[i - 1] <= 'Z') {
// If string 'a' has capital letter then it should match as capital letter cannot be converted to lower case letter.
if (j > 0 && a[i - 1] == b[j - 1]) {
dp[i][j] |= dp[i - 1][j - 1];
} else {
dp[i][j] = false;
}
} else {
// If string 'a' has lower case letter then we can either skip matching or match if that lower case letter of string 'a' matches with lower/upper case letter of string 'b'
dp[i][j] |= dp[i - 1][j];
if (j > 0 && (((a[i - 1] - 'a') == (b[j - 1] - 'a')) || ((a[i - 1] - 'a') == (b[j - 1] - 'A')))) {
dp[i][j] |= dp[i - 1][j - 1];
}
}
}
}
}
if (dp[alen][blen]) {
return "YES";
} else {
return "NO";
}
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string q_temp;
getline(cin, q_temp);

int q = stoi(ltrim(rtrim(q_temp)));

for (int q_itr = 0; q_itr < q; q_itr++) {
string a;
getline(cin, a);

string b;
getline(cin, b);

string result = abbreviation(a, b);

fout << result << "\n";
}

fout.close();

return 0;
}

string ltrim(const string &str) {
string s(str);

s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;
}

string rtrim(const string &str) {
string s(str);

s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);

return s;
}
```