Speller
SRM 247 · 2005-06-18 · by dgoodman
SRM 247 · 2005-06-18 · by dgoodman · String Manipulation
Problem Statement
Problem Statement
I need software that can read written numbers and convert them to integers.
The numbers are always between 1 and 99 inclusive, but may be misspelled.
The correct spelling of numbers is given by the following grammar, in which
'<' '>' '::=' and '|' are metacharacters and all others are literal:String number
and that returns the integer value whose correct spelling is closest to number.
The distance between two spellings is defined to be the number of characters in one
of the spellings that would need to be changed to a different character in order
to make them match, where matching is case sensitive. Two spellings of different lengths are considered
to be infinitely far apart.
- <NUMBER> ::= <ONES> | <TEEN> | <TENS> | <TENS>-<ONES>
- <ONES> ::= one | two | three | four | five | six | seven | eight | nine
- <TEEN> ::= ten | eleven | twelve | thirteen | fourteen | fifteen | sixteen | seventeen | eighteen | nineteen
- <TENS> ::= twenty | thirty | forty | fifty | sixty | seventy | eighty | ninety
The method should return -1 if there is more than one value that is closest to number.
Constraints
- number will contain between 1 and 20 characters inclusive.
- Each character in number will be between ASCII 33 and ASCII 126 inclusive.
Examples
0)
"forty-two" Returns: 42
1)
"FORTY-TWO" Returns: -1
"forty-two" and " fifty-two" are both a distance of 8 from "FORTY-TWO". No other number is closer.
2)
"eightene" Returns: 18
"eighteen" is 2 misspelled letters away from "eightene"
3)
"one-hundred" Returns: -1
4)
"fifty-fifty" Returns: 58
5)
"fi" Returns: -1
All numbers are infinitely far away, since there are no 2 character strings that represent numbers.
Submissions are judged against all 38 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Speller with a public method int value(string number) · 38 test cases · 2 s / 256 MB per case