Codeforces Round #504 A : Single Wildcard Pattern Matching

Hi Everyone,

This time I will be discussing problem A from yesterday's contest CF #504. It has quite a lot corner cases and that resulted in less AC submission than B and C of same contest. Let's cover them all.

Problem Link:
http://codeforces.com/contest/1023/problem/A

Problem Statement:
We are given two strings "S" and "T" of length "n" and "m" respectively. Ask is to transform "S" into "T" by inserting any string into "S" in place of a character '*' if and only if '*' is present.

My Approach:
Initially this seems that we need to tackle lot of corner cases as '*' may be present in start, end, middle, or not present at all in string "S". So I decided to tackle them one by one initially but at later point I thought we can keep two pointers in "T", one in start and one in end, and compare them with "S" through doing appropriate increment, decrements. I will explain how:

• Case 1: When no '*' is present. You can simply check if two strings are equal and return answer. This was reason of many WA on #71 test case, in which no '*' was present and thus if you check thinking '*' is always there, you will get WA. Test case was: S="a", T="a"
• Case 2: Length of "S" - 1 (n-1) is greater than Length of "T" (m). This will always give us "NO" because we can't insert anything in "S" to make it "T" as length of "S" is already greater than "T".
• All other Cases: Now we are sure that '*' is present in "S". Let's keep one pointer start pointing to initial position in "T", now we can check by moving forward in both "S" and "T" till we encounter '*', all characters should exactly match till '*' other wise we won't be able to make "T" from "S" as we can only insert new character in '*' place, we can't remove a character which mismatched before '*'. See image below to get more insight. Once we encounter a '*' in "S", we keep position of start stored. Now let's take another pointer end which points to last index in "T", again we will come backward in both "S" and "T" until '*' and check for every index's validity. Now at point of again encountering '*', we need to check for only one validity, which is [start<=end]. Why? Because it means that we have matched in "T" until an index start from starting and an index end from ending. Thus we can insert T[start+1, end-1] in S['*'] and "S" will match to "T".

Why it doesn't work in case of mismatch:

It is little hard to explain very clearly but I hope code will resolve some more doubts. I have commented it as well as I could.

Implementation:

I hope this editorial has helped a little. In case you have any doubts, please feel free to drop a comment. Have a Good Day!