Here's Alice and Strings, a programming challenge on hackerearth:
Two strings \$A\$ and \$B\$ comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:
- Select a prefix from the string \$A\$ (possibly empty), and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example if the string is
xyz
and we select the prefixxy
then we can convert it toyz
by increasing the alphabetical value by 1. But if we select the prefixxyz
then we cannot increase the alphabetical value.Your task is to determine if given strings \$A\$ and \$B\$ are compatible.
Input format
First line: String \$A\$
Next line: String \$B\$
Output format
For each test case, print
YES
if string \$A\$ can be converted to string \$B\$, otherwise printNO
.Constraints
$$ \DeclareMathOperator{\len}{len} 1 \leq \len(A) \leq 1\,000\,000 \\ 1 \leq \len(B) \leq 1\,000\,000 \\ $$
Can you please review my solution to it? Please comment on any aspect to improve such as readability, comment usage, further improvements on speed/memory usage, etc.
/*
HackerEarth
https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/aliceandstrings-9da62aa7/
*/
#include <iostream>
/*
Recusrsively checks if string A can be converted to B by incrementing the prefixes:
eg:
A = abaca B = cdbda
[step 1]bcbda (prefix abac incremented by 1)
[step 2]bc[b]da cd[b]da (don't take bcb as a prefix because b is already matched)
[step 3]cdbda -----> so convertible (incrementing prefix bc)
*/
bool transformable(std::string& A, std::string& B, int last_index)
{
if (A.compare(0, last_index, B, 0, last_index) == 0)
{
return true;
}
else
{
if (A[last_index] == B[last_index])
{
return transformable(A, B, --last_index);
}
else
{
if (A[last_index] > B[last_index])
{
return false;
}
else
{
while(A[last_index] != B[last_index])
{
for(int i = 0; i <= last_index; i++)
{
A[i] += ('b' - 'a');
}
}
return transformable(A, B, --last_index);
}
}
}
}
int main()
{
std::string A;
std::string B;
std::cin >> A >> B;
if (A.length() != B.length())
{
std::cout << "NO" << std::endl;
return 0;
}
if (transformable(A, B, A.length() - 1))
std::cout << "YES" << std::endl;
else
std::cout << "NO" << std::endl;
return 0;
}