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 × 100; our result so far is 2. Then we add 8 × 101; our result so far is 82. Then we add 7 × 102; 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 reduced 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 reduces 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.