An application you're working on contains an input text field where a user types in a date.
The user is instructed to type in a date in the form "<Month> <Day>" (quotes for clarity), where <Month> is the English name of the month ("January", "February", etc.) and <Day> is the day of the month, without leading zeroes.
However, a user can make errors when typing. The following model is suggested: the user always presses the correct number of keys, but he or she can mistype one key for another. Let's define the penalty for a typing error as the length of the shortest path between the key that was actually pressed and the intended key in the graph shown below.
Here red lines denote edges of length 1 and green lines denote edges of length 3. When calculating the penalty, the cases of the letters are ignored.
Obviously, the penalty for typing a correct key is 0. Now, define the distance between the input of the user and a correct date of the same length as the sum of the penalties for mistyping over all corresponding characters.
For example, distance("TopCoder", "March 31") = penalty("T", "M") + penalty("O", "A") + ... + penalty("R", "1") = 4 + 8 + 6 + 0 + 3 + 4 + 1 + 4 = 30
Given a String input, return a correct date (in the format described above) that has the smallest distance from the input. In case of a tie, return the date that is earlier in the year. |