</>Ali · LeetCode
#0008·MediumStrings

String to Integer (atoi)

LeetCode #8 · Medium · Strings · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Sequential parsing with overflow detection

Steps: 1. Skip leading whitespace 2. Check for optional sign ('+' or '-') 3. Parse digits one by one, building the result 4. Use long long to detect overflow before it happens 5. Return clamped value if overflow detected

Time
O(n)
n is the length of the string
Space
O(1)
Problem description(from LeetCode)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. Algorithm: 1. Read in and ignore any leading whitespace. 2. Check if the next character is '-' or '+'. Read this character if it is either. 3. Read in next characters until the next non-digit character or end of input is reached. 4. Convert these digits into an integer. If no digits were read, return 0. 5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], clamp the integer to stay in the range.

Examples

Example 1
Input:
s = "42"
Output:
42

Constraints

  • •0 <= s.length <= 200
  • •s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

C++ Solution

solution.cpp
class Solution {
public:
int myAtoi(string s) {
    int res = 0, idx = 0, sign = 1, n = s.size();
    lli overflowCheck = 0;
    while (idx < n && s[idx] == ' ') idx++;
    if (idx >= n) return 0;
    if (s[idx] == '-' || s[idx] == '+') {
      sign = s[idx] == '-' ? -1 : 1;
      idx++;
    }
    while (idx < n) {
      int digit = s[idx] - '0';
      if (digit < 0 || digit > 9) return sign * res;
      overflowCheck = overflowCheck * 10 + digit;
      if (overflowCheck > INT_MAX) return sign == 1 ? INT_MAX : INT_MIN;
      res = (int)overflowCheck;
      idx++;
    }

    return sign * res;
  }
};

More Strings problems