Go to “String To Integer Atoi (#8)” on Leetcode ↗

This problem combines some string manipulation with place-value math. Given a string of digits, we can turn it into a number in either direction. For example, suppose we have the string `'782'`

, which can be split into the digits `'7'`

, `'8'`

, and `'2'`

.

Going from left-to-right, starting with `0`

, we iteratively multiply the result-so-far by ten, then add the next digit. For example, we start with `0`

, multiply that by 10 and add `7`

; our result so far is `7`

. Then we multiply that by 10 and add `8`

; our result so far is `78`

. Then we multiply that by 10 and add `2`

; our final result is `782`

.

Going from right-to-left, starting with `0`

, we iteratively add the product of the next digit by its corresponding power-of-ten. For example, we start with `0`

, and add `2`

× 10^{0}; our result so far is `2`

. Then we add `8`

× 10^{1}; our result so far is `82`

. Then we add `7`

× 10^{2}; our final result is `782`

.

The rest of this problem involves different ways to extract just the digits and leading `+`

/`-`

when there are other characters involved.

# Solution 1: Use to_i

This solution would probably be considered cheating, but of course you could just use the `String#to_i`

method included in Ruby. It handles whitespaces and leading and trailing non-numeric characters exactly the way we want it; we just have to account for a result that is larger or smaller than the range allowed in the problem.

```
INT32_MAX = 2 ** 31 - 1
INT32_MIN = -1 * 2 ** 31
def my_atoi(str)
int = str.to_i
if int > INT32_MAX
INT32_MAX
elsif int < INT32_MIN
INT32_MIN
else
int
end
end
```

# Solution 2: Iterate Through Characters, Then Combine

This solution implements the general solution outlined in the problem itself. It iterates through each character in the input string, ignoring any whitespace in the beginning of the string (before it has detected a number yet). Once it comes across a non-whitespace character, it records a leading `+`

or `-`

if it is one, then reads as many digits as it can following that. It stops processing the string once it stops reading digits — in this way, it ignores “additional characters after those that form the integral number”. Then, the array of digits are combined left-to-right, and finally we adjust for negative numbers and the range allowed in the problem.

```
INT32_MAX = 2 ** 31 - 1
INT32_MIN = -1 * 2 ** 31
def my_atoi(str)
digits = []
found_number = false
is_negative = false
str.each_char do |char|
next if whitespace?(char) && !found_number
if !found_number
found_number = true
if char == '-'
is_negative = true
next
elsif char == '+'
is_negative = false
next
end
end
if found_number && digit?(char)
digits << char
else
break
end
end
return 0 if digits.empty?
result = 0
digits.each do |char|
result = result * 10 + char_to_number(char)
end
int = is_negative ? -1 * result : result
if int > INT32_MAX
INT32_MAX
elsif int < INT32_MIN
INT32_MIN
else
int
end
end
def whitespace?(char)
char =~ /\s/
end
def digit?(char)
char =~ /\d/
end
def char_to_number(char)
case char
when '0' then 0
when '1' then 1
when '2' then 2
when '3' then 3
when '4' then 4
when '5' then 5
when '6' then 6
when '7' then 7
when '8' then 8
when '9' then 9
end
end
```

# Solution 3: Iterate Through Characters and Reduce

This solution is the same as the previous, except instead of accumulating digits in an array to be combined later, digits are combined into a resulting number as we go via the `reduce`

method.

The `Enumerable#reduce`

method “reduces” an array of values down into one value by executing some code on each value and storing each intermediate result in an “accumulator”. This accumulated value is also provided to the code that each step executes, and this allows the result to be built up. For example, `reduce`

can be used to calculate the sum of an array of numbers:

```
[3, 8, 10, 18, -2].reduce(0) do |accumulated_value, next_value|
accumulated_value + next_value
end
```

In this example, we `reduce`

over the array, starting with `0`

as an initial value (the first `accumulated_value`

). In the first iteration of the block, `accumulated_value`

is `0`

and `next_value`

is `3`

. The block evaluates to `0 + 3`

, and so `3`

becomes the next `accumulated_value`

. `3`

is paired with `8`

as the `next_value`

; `3 + 8`

evaluates to `11`

, which becomes the next `accumulated_value`

… and so on. At the end, this `reduce`

expression evaluates to `37`

.

This solution for string-to-integer uses `reduce`

to build up the resulting number digit-by-digit (going left-to-right) — this is specified by the `if`

expression at the end of the `reduce`

block: `if found_number && digit?(char)`

, then evaluate to `results_so_far * 10 + char_to_number(char)`

.

In other places, we use `next`

and `break`

. In Ruby, `next`

skips the rest of the code in a block and goes to the next iteration of the enumeration it’s contained in. In other languages (like Javascript), you might provide an anonymous or arrow function to `reduce`

, and within that function, you call `return`

to return early. In Ruby, `return`

always exits the **containing method**, so using `return`

in this case would exit the entire `my_atoi`

method, not just the `reduce`

block. Similarly, `break`

is used to skip the remaining iterations of the block. In both cases, you can provide a value (such as `next result_so_far`

or `break result_so_far`

) to serve as the “return” value — `next result_so_far`

makes the current `result_so_far`

become the `result_so_far`

for the next iteration, while `break result_so_far`

makes the entire `reduce`

d value be the current `result_so_far`

.

```
INT32_MAX = 2 ** 31 - 1
INT32_MIN = -1 * 2 ** 31
def my_atoi(str)
found_number = false
is_negative = false
result = str.each_char.reduce(0) do |result_so_far, char|
next result_so_far if whitespace?(char) && !found_number
if !found_number
found_number = true
if char == '-'
is_negative = true
next result_so_far
elsif char == '+'
is_negative = false
next result_so_far
end
end
if found_number && digit?(char)
result_so_far * 10 + char_to_number(char)
else
break result_so_far
end
end
int = is_negative ? -1 * result : result
if int > INT32_MAX
INT32_MAX
elsif int < INT32_MIN
INT32_MIN
else
int
end
end
def whitespace?(char)
char =~ /\s/
end
def digit?(char)
char =~ /\d/
end
def char_to_number(char)
case char
when '0' then 0
when '1' then 1
when '2' then 2
when '3' then 3
when '4' then 4
when '5' then 5
when '6' then 6
when '7' then 7
when '8' then 8
when '9' then 9
end
end
```

# Solution 4: Extract Digits and Reduce

This solution uses a regex to extract the first set of digits from the input string, then `reduce`

s over them, going right-to-left, to compute the result.

This solution might be more clever than practical, but it was fun to figure out 😆

First, it calls `String#strip`

to remove whitespace at the beginning and end of the string.

Then, it uses a regex to match and capture digits: `/^([+-]?\d+)/`

- The
`^`

makes it start matching from the beginning of the string — this means it won’t match digits starting in the middle of a string, which is the correct way to handle a case like “words and 987”. - The parenthesized bit after represents a regex capture group, meaning we want to “capture” or save the original characters that match whatever is inside the parentheses.
- What do we want to capture? It can start with a
`+`

or`-`

, represented by the character group`[+-]`

. There can only be zero or one of either; this is represented by the`?`

. - Then we have one or more digits, represented by
`\d+`

.

Rubular is a great site for playing with regexes.

If there is a match, then everything we’re interested in is in the first captured result. For example, `'4193 with words'.match(/^(-?\d+)/).captures.first`

is `'4193'`

.

Then we take this result, and:

`reverse`

it to go right-to-left;- iterate over
`each_char`

, - making sure the iteration also happens
`with_index`

so we can determine place-value, - and
`reduce`

starting from`0`

. With this setup, the first argument to the`reduce`

block is still the accumulator; the second argument is the “next value”. In this case, the “next value” is an array containing the actual next value as well as its index. Ruby allows this array to be destructured by using the parenthesized variables`(char, index)`

. To illustrate this further with a simple example, if we have`(a, b) = [1, 2]`

, that would assign`1`

to`a`

and`2`

to`b`

.

```
INT32_MAX = 2 ** 31 - 1
INT32_MIN = -1 * 2 ** 31
def my_atoi(str)
str_without_leading_trailing_spaces = str.strip
if (match = str_without_leading_trailing_spaces.match(/^([+-]?\d+)/))
number_string = match.captures.first
int = number_string.reverse.each_char.with_index.reduce(0) do |result, (char, index)|
case char
when '-'
result * -1
when '+'
result
when /\d/
result + char_to_number(char) * 10 ** index
else
return 0
end
end
if int > INT32_MAX
INT32_MAX
elsif int < INT32_MIN
INT32_MIN
else
int
end
else
return 0
end
end
def char_to_number(char)
case char
when '0' then 0
when '1' then 1
when '2' then 2
when '3' then 3
when '4' then 4
when '5' then 5
when '6' then 6
when '7' then 7
when '8' then 8
when '9' then 9
end
end
```

There’s no particular reason this solution needed to go right-to-left, other than to illustrate how it would work. Going left-to-right would work as well.