Problem 8 - String to Integer Atoi (Medium)
Code for this problem is available at https://github.com/scprogramming/LeetcodeExplained/tree/master/Problem%208%20-%20String%20to%20Integer%20Atoi%20(Medium)
Problem: Implement the atoi function, which converts a string into an integer
Problems involving reimplementing system and built in programming functions are great practice for learning programming techniques and logic. For this problem, it is very helpful to first outline all of the cases and situations we could encounter in the problem.
Here are the cases involved in this problem:
- If the string contains any whitespace characters, they should be removed
- The string can contain exactly one non whitespace character at the beginning that is either a "+" or "-" sign
- If there are any other characters before the digit, the result is 0
- If there are any characters after the digits, they are ignored
- If the number is greater than 231 - 1, or less than -231, the max value 231 - 1, or min value -231 is returned instead
Before starting with coding, let's do a few quick examples to get an idea of the output we are expecting.
This case is the easiest case we will encounter. In this case, we can just directly convert and we are done.
Input: " -42"
This case involves a negative sign, which we keep since it is the first character
Remember that everything from the first text character onwards is ignored, so everything after "-" is excluded, giving us just 4.
Input: "text 4"
Any text before the number that isn't "+" or "- "results in a failure to parse.
With these examples in mind, let's now program a solution.
To start, we are going to strip the provided string to remove any whitespace that exists. From here, we can iterate the string to start checking for valid numbers. First, we check the first character to determine if it is not a digit, and not "+" or "-". If this case occurs, we set valid to false, since we know that the first character, we see is text, and not a numeric sign, meaning the input is invalid. If it isn't this case, we check for a "-" or a digit. In either of these cases, we just append the result.
Notice that in the first set of checks we ignore the "+" case. This is because if we see a "+", it is valid, but we don't need to append it anywhere, so we are safe to just ignore it. Once we have dealt with the first character, we are free to parse the rest. If we encounter a non-digit, we set i to the length of the string. This will stop the iteration without setting valid to false, since it can be valid with text in the middle but shouldn't parse any further. The default case is that we see an integer, which we can just append.
From here, we just need two more checks and we are done.
Our last two checks are to see if valid is still true. If it isn't, we set the output to 0 and return. If it is valid, we check if the result is too large or too small and adjust to as required. After this, we return the result, and we are done.
Now that we have a working algorithm, we can analyze the time complexity to see how it runs. You'll notice we only loop the input once, so in the worst case, we do n iterations, where n is the number of characters in the string. Therefore, this algorithm executes in O(n) time complexity.