# LeetCode 8: String to Integer (atoi) ## Problem Restatement We are given a string `s`. We need to implement `myAtoi(s)`, which converts the beginning of the string into a signed 32-bit integer. The parsing follows these rules: 1. Ignore leading spaces. 2. Read an optional sign, either `+` or `-`. 3. Read digits until a non-digit character appears. 4. If no digits are read, return `0`. 5. Clamp the result into the signed 32-bit integer range. The signed 32-bit range is: ```text [-2147483648, 2147483647] ``` If the value is smaller than `-2147483648`, return `-2147483648`. If the value is larger than `2147483647`, return `2147483647`. The current LeetCode statement uses these parsing and clamping rules. ## Input and Output | Item | Meaning | |---|---| | Input | A string `s` | | Output | A signed 32-bit integer | | Leading spaces | Ignored | | Optional sign | One `+` or `-` may appear after spaces | | Digits | Read until the first non-digit | | Overflow | Clamp to signed 32-bit range | Example function shape: ```python def myAtoi(s: str) -> int: ... ``` ## Examples Example 1: ```text s = "42" ``` There are no leading spaces and no sign. Read digits: ```text 42 ``` Output: ```text 42 ``` Example 2: ```text s = " -042" ``` Ignore spaces. Read sign: ```text - ``` Read digits: ```text 042 ``` The numeric value is `42`. Apply the sign: ```text -42 ``` Output: ```text -42 ``` Example 3: ```text s = "1337c0d3" ``` Read digits until the first non-digit: ```text 1337 ``` Stop at: ```text c ``` Output: ```text 1337 ``` Example 4: ```text s = "words and 987" ``` The first non-space character is not a sign or digit. No conversion can be made. Output: ```text 0 ``` Example 5: ```text s = "-91283472332" ``` The parsed value is less than `-2147483648`. So we clamp it. Output: ```text -2147483648 ``` ## First Thought: Use Built-in Conversion In Python, one might try to clean the string and call `int`. But this quickly becomes messy because `atoi` does not parse the whole string. For example: ```text "1337c0d3" ``` should return: ```text 1337 ``` But direct integer conversion would fail because the string contains letters. The problem is mainly about implementing the parser manually. ## Key Insight We can read the string once from left to right. The parser has four phases: | Phase | Action | |---|---| | Whitespace | Skip leading spaces | | Sign | Read one optional sign | | Digits | Accumulate digits | | Stop | Stop at first non-digit | While reading digits, build the number using: ```text result = result * 10 + digit ``` For example: ```text "4193" ``` is built as: ```text 0 4 41 419 4193 ``` ## Algorithm 1. Set `i = 0`. 2. Skip leading spaces. 3. Read optional sign. 4. Initialize `result = 0`. 5. While `i` is inside the string and `s[i]` is a digit: - Convert `s[i]` into a digit. - Update `result`. - Clamp early if the value becomes too large. 6. Return `sign * result`. ## Correctness The algorithm skips exactly the leading spaces before parsing. After spaces, it reads at most one sign. If no sign exists, the sign remains positive. Then it reads consecutive digits only. The moment a non-digit appears, parsing stops, which matches the required `atoi` behavior. During digit parsing, each new digit is appended to the right side of the current value: ```text result = result * 10 + digit ``` So after reading `k` digits, `result` equals the integer represented by exactly those `k` digits. If no digits are read, `result` remains `0`, so the function returns `0`. If the parsed value exceeds the signed 32-bit range, the algorithm returns the correct boundary value. Therefore the algorithm returns exactly the integer defined by the parsing rules. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each character is inspected at most once | | Space | `O(1)` | Only counters and integer variables are stored | ## Implementation ```python class Solution: def myAtoi(self, s: str) -> int: MIN_INT = -2**31 MAX_INT = 2**31 - 1 n = len(s) i = 0 while i < n and s[i] == " ": i += 1 sign = 1 if i < n and s[i] in ["+", "-"]: if s[i] == "-": sign = -1 i += 1 result = 0 while i < n and s[i].isdigit(): digit = ord(s[i]) - ord("0") result = result * 10 + digit if sign == 1 and result > MAX_INT: return MAX_INT if sign == -1 and -result < MIN_INT: return MIN_INT i += 1 return sign * result ``` ## Code Explanation Define the integer boundaries: ```python MIN_INT = -2**31 MAX_INT = 2**31 - 1 ``` Use an index to scan the string: ```python i = 0 ``` Skip leading spaces: ```python while i < n and s[i] == " ": i += 1 ``` Read the optional sign: ```python if i < n and s[i] in ["+", "-"]: if s[i] == "-": sign = -1 i += 1 ``` Build the integer digit by digit: ```python digit = ord(s[i]) - ord("0") result = result * 10 + digit ``` Clamp overflow: ```python if sign == 1 and result > MAX_INT: return MAX_INT if sign == -1 and -result < MIN_INT: return MIN_INT ``` Finally apply the sign: ```python return sign * result ``` ## Testing ```python def run_tests(): s = Solution() assert s.myAtoi("42") == 42 assert s.myAtoi(" -042") == -42 assert s.myAtoi("1337c0d3") == 1337 assert s.myAtoi("0-1") == 0 assert s.myAtoi("words and 987") == 0 assert s.myAtoi("-91283472332") == -2147483648 assert s.myAtoi("91283472332") == 2147483647 assert s.myAtoi("+1") == 1 assert s.myAtoi("+-12") == 0 assert s.myAtoi(" +0 123") == 0 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `"42"` | Basic positive number | | `" -042"` | Spaces, sign, and leading zero | | `"1337c0d3"` | Stops at first non-digit | | `"0-1"` | Stops after valid digit sequence | | `"words and 987"` | No valid initial number | | `"-91283472332"` | Negative clamp | | `"91283472332"` | Positive clamp | | `"+1"` | Explicit positive sign | | `"+-12"` | Invalid sign sequence | | `" +0 123"` | Stops after zero before space |