After reviewing the Meller watch, it’s time for some more IT related stuff in the blog. Thus, I have decided to do what I usually do when I want to write some article and I do not know what to write about – I go to the codeforces.com and I take a look at their problems. As far as I have decided to start coding a bit in C++, the idea was to solve a problem with C# and then solve it with C++. Just for the sake of learning something new.
The problem was looking like this:
Mike has a string s consisting of only lowercase English letters. He wants to change exactly one character from the string so that the resulting one is a palindrome.
A palindrome is a string that reads the same backward as forward, for example strings “z“, “aaa“, “aba“, “abccba” are palindromes, but strings “codeforces“, “reality“, “ab” are not.
The first and single line contains string s (1 ≤ |s| ≤ 15).
Print “YES” (without quotes) if Mike can change exactly one character so that the resulting string is palindrome or “NO” (without quotes) otherwise.
It looks pretty much easy as anything. There are at least 10 ways to solve a problem like this with C# (I am not joking), and if I had to come up with the smartest one, it would have been something like this:
- Reverse the string and compare it to the half with the initial string
- If there are more than two differences, write “NO”.
Well, it was not that easy. It was two steps more difficult, and this time it was good, that I had the tests to see where I was failing. 🙂 The idea is that you must be able to change exactly one character, in order to write “YES”. If you have a palindrome from the beginning and the number of characters is equal, then you are not able to write “YES”. Anyhow, interesting first problem, just proving that one should never assume that he has completely understood the problem. These were my results:
As you can imagine, the solution with C# is quite trivial, I did not care to write it in a better way:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class MikeAndPalindrome { static void Main() { string strInput = Console.ReadLine(); string strInputRev = Reverse(strInput); int intLenInterest = strInput.Count() / 2; int intResult = 0; for (int i = 0; i < intLenInterest; i++) { if (!strInput[i].Equals(strInputRev[i])) { intResult++; } } if ((intResult==1) || ((intResult==0)&&(strInput.Count() % 2==1))) { Console.WriteLine("YES"); }else { Console.WriteLine("NO"); } } public static string Reverse(string s) { char[] charArray = s.ToCharArray(); Array.Reverse(charArray); return new string(charArray); } } |
After all, if it is good enough for the 100+ tests of CodeForces, it is good enough for VitoshAcademy.
The tricky part was to take the solution and to rewrite it with C++. It was not a pleasant task, as far as I had to google almost every second operator. But, it was kind of useful and partially fun. Furthermore, I now know how a C++ solution should look like in order to pass the tests in CodeForces.com.
Are you interested? Here it is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string strInput; string strInputRev; cin >> strInput; strInputRev = strInput; reverse(strInputRev.begin(), strInputRev.end()); int intLenInterest = strInput.length() / 2; int intResult = 0; for (int i = 0; i < intLenInterest; i++) { if (!(strInput[i]==strInputRev[i])) { intResult++; } } if ((intResult==1) || ((intResult==0)&&(strInput.length()%2==1))) { cout << "YES"; } else { cout << "NO"; } return 0; } |
Yup! 🙂