Solution: String to Integer (atoi)

Statement#

Write a function, myAtoi(string s), that converts a string to a 32–bit signed integer. It is equivalent to the atoi function in C/C++.

The myAtoi function reads the input string, s, from left to right for the conversion process. The conversion begins by removing any leading whitespace. Then, it checks if the next character is '+' or '-'. If it's '-', it implies that the result is negative, and there must be a '-' sign in front of the resulting integer. Otherwise, '+' implies that the result is positive, so there is no need to add a '+' sign in front of the resulting integer. For example, "-$25$" converts to -$25$, and "+$91$" converts to $91$. However, if neither is present, assume the result is positive.

After removing the whitespace, if the first non-space character is not a sign character, '+' or '-', but a non-digit character, i.e., an English letter or the period '$.$', the function stops processing further and returns $0$. For example, the strings "$\:\:\:$One$1$" and "$\:\:\:$$.5$" convert to $0$. Additionally, if the first non-space character is a sign character, '+' or '-', and the next character is a non-digit character (including the space character), the function returns $0$. For example, the strings "$\:\:\:$+$.23$" , "$\:\:\:$-$\:\:49$", and "$\:\:\:$+R$345$" convert to $0$.

The function continues to read the string while checking if the subsequent character is a digit and stops reading when a non-digit character is encountered. For characters that are digits, the function concatenates them. Next, it transforms the collected digits into their corresponding integer value. It ensures that the sign value, if any, is adjusted to the resulting integer. For example, "$3$" transforms to $3$, "$0045$" changes to $45$, "-$8$" results in -$8$ and "+$640$" becomes $640$. The second example implies that there is no need to add any leading zeros in the final answer.

Finally, the function checks if the resulting integer goes out of the range of a 32–bit signed integer, $[$-$2^{31}$, $2^{31}$ - $1]$. It returns -$2^{31}$ if it's less than -$2^{31}$ and returns $2^{31}$ if it's greater than $2^{31}$. Otherwise, if the resulting integer is within the defined range, return it as the final output.

Note: The space character (' ') and the period ('$.$') are part of the non-digit characters. Therefore, they will get ignored and won't affect the final answer. For example, "$7\:\: 9\:\:0$" converts to $7$ and "$85.9$" converts to $85$.

Constraints:

• $0 \leq$ s.length $\leq 200$

• The string s may have:

  • digit characters from $0$–$9$.

  • non-digit characters, including lower-case and upper-case English letters, space character (' '), period ('$.$'), and sign characters ('+' and '-').

Solution#

We'll begin by initializing an iterator i that will help us keep track of the characters in s while we process it. Then, we use this iterator to skip all the leading whitespace characters from the input string, s. This task is straightforward because, in the context of this problem, only space characters, ' ', are considered as whitespace. We iterate over each character in s and increment i by 1 whenever we encounter a space character. This process continues until we encounter a non-space character. At that point, we'll stop because i should now point to the non-space character.

The next step is to check if the current character, s[i], is a positive '+' or a negative '-' sign character. If s[i] == '-', it means the number is negative, so we set the variable, sign, to -$1$. Otherwise, if it's a '+', assuming the number is positive, we don't change the value of sign, which is $1$. Either way, we increment i to move it to the next character in s.

Next, we check whether the current character, s[i], is a non-digit character. If it is, we stop reading the string further and return $0$. Otherwise, we start to extract the digits from s, and convert them into their respective numeric value. We store the integer representation of digits in a variable, result. To achieve this, we first check whether s[i] is a digit. If it is, it should lie in the range $0$ to $9$. Then, we convert the identified digit to its numeric value by subtracting the ASCII value of $0$ from the ASCII value of s[i].

Once we have the numerical value of s[i], we concatenate it with the already extracted digits that are stored in result. For this, we we multiply result by $10$ and then add the numerical value of s[i] to it. This step shifts the existing digits in result to the left by one position. For example, if result is $12$ and the digit that needs to be added is $5$, then result $\times \:12$ would yield $120$, and $120$ + $5$ would just put the digit in the place of $0$, leading to a value $125$.

While reading and storing the digits from s, we'll stop if:

• We reach the end of the string s.

• We encounter a non-digit character.

• The value in result goes beyond the limit for a 32-bit signed integer and leads to an overflow.

We check for the potential integer overflow by subtracting the digit from the limit for a 32-bit signed integer and dividing it by $10$. If the result violates the limit, we don't append the current digit to the result. Instead, we just return the maximum or minimum value that lies in the 32-bit signed integer range.

Finally, we apply the determined sign to the result by multiplying the result with sign, and return the resulting integer as the final output.

Let’s look at the following illustration to get a better understanding of the solution:

Now, let’s look at the code for the solution below:

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the length of the input string s. This is because we iterate through the input string once, character by character, without nested loops or recursive calls.

Space complexity#

The space complexity of this solution is $O(1)$.