String To Integer - Leetcode #8 Short & Simple Solution
Updated: Jun 3, 2022
Problem Statement
In our previous article we solved the longest distinct substring problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 8 problem.
Implement myAtoi(string s) function, which converts a string to a 32-bit signed integer.
Conditions for converting string to integer:
Read in and ignore any leading whitespace.
Check if the first character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.
Return the integer as the final result.
Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example
Example 1
Input: s = "42"
Output: 42Example 2
Input: s = " -42"
Output: -42Example 3
Input: s = "4193 with words"
Output: 4193Solution
This problem is rated medium difficulty in leetcode. However it is a pretty straightforward solution if you understand the logic behind converting a string to an integer. Rest of the handling is needed mainly to cover boundary conditions for various types of input values.
How to convert a string type to an integer type?
Given a string s how can we convert this to an integer? One way to do this is by manipulating the ASCII value of characters. Each character in a string has a specific ASCII value associated with it. Numeric values 0 - 9 have an ASCII value in the range 48 - 57(For more details refer ASCII table). We can use this information to convert a character to an integer type. Lets see how:
For each character in the given string we need to do the following steps in order to convert it into an integer:
First we need to check if the given character represents a numeric value.This can be done by checking if its ASCII value is in the range 48 - 57.
Once we determine that the character represents a numeric value, we convert this character type into an integer type. To do this we need to subtract the characters' ASCII value with 48 (which is the ASCII value of number 0).
Once the character is converted to an integer we need to move the integer to its correct base position in result by multiplying the previous result with 10 and adding the answer obtained in step 2 to it.
These three steps can be represented by the formula:
result = (result * 10)+ (ASCII value of current character - ASCII value of '0')
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Lets understand this with an example. Consider s = "123" is the given string. Lets take a integer type variable result to store our result. Initially result = 0.
We will start with the first character in string s = "123" i.e. character'1'. First step is to check if it is a numeric value, so we get the ASCII value of '1', which is 49, this is in the range 48 - 57, so we can conclude it is a numeric value.
Next step is to subtract the ASCII value of 1 with ASCII value of 0, i.e. 49 - 48 = 1, which is our required integer type value. So now we have converted the character '1' to its integer representation 1.
Next we move 1 to its correct base position in result by using the above formula. So at the end of first iteration result will be , result = result * 10 + (49-48) = 0 * 10 +1 = 1.
Next we move on to the second character in string "123", i.e. character '2'. So,
result = (result * 10)+ (ASCII value of '2' - ASCII value of '0')
Thus result = (1* 10)+ (50 - 48) = 10 + 2 = 12. As you can see we have successfully converted the first two characters of the string s into integer format.
Next we move on to the 3rd character '3'. Again we calculate result using the same formula.
result = (result * 10)+ (ASCII value of '3' - ASCII value of '0')
Thus result = (12* 10)+ (51 - 48) = 120 + 3 = 123, which our final result.
How to handle input values containing +/- sign?
We take a int variable, lets call it signMultiplier. We make signMultiplier = -1 for input values starting with '-' sign and 1 for input values starting with '+'. If the input contains any of +/- sign we start processing the string from 2nd character and we multiply the signMultiplier to our final result.
Code
Language: Go
Language: Python
Complexity Analysis
Time Complexity: O(n)
The worst case time complexity of this algorithm is O(n) since we have to go through each character in the string at least once to fully convert the given string to integer. n here is the length of the string.
Space Complexity: O(1)
No extra space is used.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now.
Comentários