SISLOVE - Editorial

h1ashdr_gon · August 1, 2015, 3:37pm

PROBLEM LINK:

Practice

Contest

Author: Shivam Kapoor

Tester: Rishabh Prasad

Editorialist: Shivam Kapoor

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Implementation, Basic-Programming, Strings

PROBLEM:

You are given the incorrect spellings of number names (from zero to ten (inlusive)) with exactly one mistake. You need to print the numerical value of the correct spelling.

QUICK EXPLANATION:

This problem can be easily solved with brute-force in O(N²) time limit because of lower value of constraints. Maintain an array of strings with the correct spellings and one with the corresponding numerical values. Loop through the whole array for the given spelling. If more than 1 mismatch is found move to the next word. This problem can also be solved using Edit-Distance.

EXPLANATION:

We start off by creating an array of strings with the correct representation of the number names starting from 0-9. Note that an array of string is nothing but a Double dimensional array.
Since we need to print the numerical value of the correct answer we also maintain an integer array with values 0-9.
Next, we input the incorrect spelling and match it with every word in the array.NOTE : We only need to compare with those values which have the same length as that of the input because as per the question the length is not altered. So if input.length() != array[i].length() there is no point in proceeding further, we simply move to the next index in the array. Now once a match in length is found, we compare every corresponding character and once a match is found we increment a counter or flag variable every time. Once the value of this counter variable exceeds 1, we make it zero and move to the next word. This is because there is EXACTLY one mistake in the word. Once the answer is found, we store the INDEX of that word in the array and print the corresponding value in our integer array i.e integerarray[i] since they are correspondingly one and the same!

Here is the pseudo-code of the above implementation.

string str[10]={"zero","one","two","three","four","five","six","seven","eight","nine"}
int arr[10]={0,1,2,3,4,5,6,7,8,9}
for(i=0 to 9)	
  count=0
  if(length of(str[i])==length of (word))
  for(j=0 to length(word))
   if(word[j]!=str[i][j]) //jth character of ith string
     count++
   if(count>1) //More than 1 mismatch has been found so this cannot be the answer
      count=0; //For the next iteration
      break
    if(count==1) //Reuired condition is met
    minpos=i //Store the index of this word in the array
    break
print arr[minpos] //Final answer

C users can use char* str[ ] in place of strings.

ALTERNATIVE SOLUTION:

This problem can also be solved via Edit Distance and requires the knowledge of Dynamic Programming. This is a pretty straightforward question in dynamic programming.
You just have to check=>

if(minEditDistance(incorrect spelling,correct spelling)==1)
If so, then print the integral value of correct spelling.

Here is a short pseudo code of the above implementation.

if(minEditDistance(x,"one")==1)
print 1
if(minEditDistance(x,"two")==1)
print 2
if(minEditDistance(x,"three")==3)
print 3

…and so on.This code can be optimized also but this is just to give the basic idea.

NOTE This solution is also applicable if the question was extended to more than 1 mistake. In fact this would be more feasible.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here. (C++)

Tester’s solution can be found here. (Python)