Solving the LeetCode "String to Integer (atoi)" Problem in Go

Difficulty: Medium | Tags: String

Introduction

The "String to Integer (atoi)" problem requires converting a string to a 32-bit signed integer while adhering to specific parsing rules. This problem tests your ability to handle edge cases, whitespace, signs, and overflow conditions.

Problem Analysis

The problem involves parsing a string into an integer by following a sequence of steps: ignoring leading whitespace, handling optional signs, reading digits until a non-digit character is encountered, and clamping the result to the 32-bit signed integer range. Examples demonstrate scenarios like leading zeros, mixed characters, and overflow.

Solution Approach

The solution involves iterating through the string while applying the parsing rules. We first skip whitespace, then check for a sign, followed by reading digits. During digit processing, we check for overflow by comparing intermediate results against the 32-bit integer limits.

Go Implementation

func myAtoi(s string) int {
    i := 0
    n := len(s)
    // Step 1: Ignore leading whitespace
    for i < n && s[i] == ' ' {
        i++
    }
    // Step 2: Handle sign
    sign := 1
    if i < n && (s[i] == '+' || s[i] == '-') {
        if s[i] == '-' {
            sign = -1
        }
        i++
    }
    // Step 3: Read digits
    result := 0
    for i < n && s[i] >= '0' && s[i] <= '9' {
        digit := int(s[i] - '0')
        // Step 4: Check for overflow
        if result > (1<<31 - 1 - digit) / 10 {
            if sign == 1 {
                return 1<<31 - 1
            } else {
                return -1 << 31
            }
        }
        result = result * 10 + digit
        i++
    }
    return result * sign
}

Complexity Analysis

The algorithm processes each character in the string exactly once, resulting in a time complexity of O(n), where n is the length of the string. The space complexity is O(1) as no additional data structures are used.

Testing and Examples

Test cases should include strings with leading whitespace, signs, leading zeros, non-digit characters, and values near the 32-bit integer limits. Examples:

• "42" → 42
• " -042" → -42
• "1337c0d3" → 1337
• "0-1" → 0
• "words and 987" → 0
• "2147483648" → 2147483647 (overflow)

Best Practices and Tips

Key takeaways include handling edge cases early, avoiding unnecessary conversions, and checking for overflow during digit processing. Use constants for 32-bit limits to improve readability and maintainability.