# 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**^{2}) 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)

# RELATED PROBLEMS:

http://www.codechef.com/problems/CHEFSTLT

https://www.codechef.com/problems/SEATSR