How to parse a string to an integer without librar

Question

I was recently asked this question in an interview:

"How could you parse a string of the form '12345' into its integer representation 12345 without using any library functions, and regardless of language?"

I thought of two answers, but the interviewer said there was a third. Here are my two solutions:

Solution 1: Keep a dictionary which maps '1' => 1, '2' => 2, etc. Then parse the string one character at a time, look up the character in your dictionary, and multiply by place value. Sum the results.

Solution 2: Parse the string one character at a time and subtract '0' from each character. This will give you '1' - '0' = 0x1, '2' - '0' = 0x2, etc. Again, multiply by place value and sum the results.

Can anyone think of what a third solution might be?

Thanks.

Answer 1

You could always try a binary search through a massive look up table of string representations!

No-one said anything about efficiency... :-)

Answer 2

Artelius's answer is extremely concise and language independent, but for those looking for a more detailed answer with explanation as well as a C and Java implementation can check out this page:

http://www.programminginterview.com/content/strings

Scroll down (or search) to "Practice Question: Convert an ASCII encoded string into an integer."