We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

String to Integer (atoi)

Difficulty: Medium

Problem Description

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The algorithm for myAtoi(string s) follows specific steps to handle whitespace, signedness, and conversion while ensuring the result stays within the 32-bit signed integer range.

Key Insights

  • Ignore leading whitespace.
  • Determine the sign based on the presence of '+' or '-'.
  • Skip leading zeros when converting to integer.
  • Handle overflow and underflow by clamping the result to the range of [-2^31, 2^31 - 1].

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as we are using a constant amount of space.

Solution

The solution involves:

  1. Traversing the string to ignore leading whitespace.
  2. Checking for a sign indicator ('+' or '-') and adjusting a sign variable accordingly.
  3. Iterating through the characters to read digits while skipping leading zeros.
  4. Converting the digits into an integer and checking for overflow conditions to ensure the result is within the 32-bit signed integer range.

Code Solutions

def myAtoi(s: str) -> int:
    i = 0
    n = len(s)
    
    # Step 1: Ignore leading whitespace
    while i < n and s[i] == ' ':
        i += 1

    # Step 2: Check for sign
    sign = 1
    if i < n and (s[i] == '-' or s[i] == '+'):
        sign = -1 if s[i] == '-' else 1
        i += 1

    # Step 3: Convert digits
    result = 0
    while i < n and s[i].isdigit():
        digit = int(s[i])
        
        # Check for overflow
        if result > (2**31 - 1) // 10 or (result == (2**31 - 1) // 10 and digit > 7):
            return 2**31 - 1 if sign == 1 else -2**31
        
        result = result * 10 + digit
        i += 1

    return sign * result
← Back to All Questions