HomeLeetcode8. String to Integer (atoi) - Leetcode Solutions
Leetcode

8. String to Integer (atoi) – Leetcode Solutions

Declan Clarke

Description:

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

  1. Whitespace: Ignore any leading whitespace (" ").
  2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present.
  3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
  4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

Examples:

Example 1:

Input: s = "42"

Output: 42

Explanation:

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
Example 2:

Input: s = " -042"

Output: -42

Explanation:

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros ignored in the result)
               ^

Solution in Python:

To implement the myAtoi function in Python that converts a string to a 32-bit signed integer, we can follow the specified algorithm step-by-step. Here is the implementation with detailed comments:

Python
class Solution:
    def myAtoi(self, s: str) -> int:
        # Define constants for the 32-bit integer limits
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        
        # Initialize index, sign, and result
        i = 0
        n = len(s)
        sign = 1
        result = 0
        
        # Step 1: Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1
        
        # Step 2: Check for the sign
        if i < n and (s[i] == '+' or s[i] == '-'):
            sign = -1 if s[i] == '-' else 1
            i += 1
        
        # Step 3: Convert digits to integer
        while i < n and s[i].isdigit():
            digit = int(s[i])
            
            # Check for overflow and clamp the value if necessary
            if result > (INT_MAX - digit) // 10:
                return INT_MIN if sign == -1 else INT_MAX
            
            result = result * 10 + digit
            i += 1
        
        # Apply the sign to the result
        result *= sign
        
        return result

# Example usage:
solution = Solution()
print(solution.myAtoi("42"))        # Output: 42
print(solution.myAtoi("   -042"))   # Output: -42
print(solution.myAtoi("1337c0d3"))  # Output: 1337
print(solution.myAtoi("0-1"))       # Output: 0
print(solution.myAtoi("words and 987"))  # Output: 0

Explanation:

  1. Define Constants:
    • INT_MAX and INT_MIN represent the maximum and minimum values of a 32-bit signed integer, respectively.
  2. Initialize Variables:
    • i is the current index in the string.
    • n is the length of the string.
    • sign is initialized to 1 and will be set to -1 if a ‘-‘ sign is encountered.
    • result will store the converted integer value.
  3. Skip Leading Whitespace:
    • The while loop skips any leading spaces in the string.
  4. Check for the Sign:
    • If the current character is ‘+’ or ‘-‘, update the sign variable accordingly and move the index i to the next character.
  5. Convert Digits to Integer:
    • The while loop processes the digits of the string, converting them to an integer.
    • It checks for potential overflow before updating the result. If an overflow is detected, it returns INT_MIN or INT_MAX accordingly.
  6. Apply the Sign:
    • Multiply the result by sign to get the final result.
  7. Return the Result:
    • The final result is returned after applying the sign.

This implementation handles all specified edge cases, including leading whitespace, presence of a sign, non-digit characters, and overflow/underflow scenarios.

Solution in Javascript:

JavaScript
/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    // Define constants for the 32-bit integer limits
    const INT_MAX = 2**31 - 1;
    const INT_MIN = -(2**31);

    // Initialize index, sign, and result
    let i = 0;
    let n = s.length;
    let sign = 1;
    let result = 0;

    // Step 1: Skip leading whitespace
    while (i < n && s[i] === ' ') {
        i++;
    }

    // Step 2: Check for the sign
    if (i < n && (s[i] === '+' || s[i] === '-')) {
        sign = (s[i] === '-') ? -1 : 1;
        i++;
    }

    // Step 3: Convert digits to integer
    while (i < n && s[i] >= '0' && s[i] <= '9') {
        let digit = s[i].charCodeAt(0) - '0'.charCodeAt(0);

        // Check for overflow and clamp the value if necessary
        if (result > Math.floor((INT_MAX - digit) / 10)) {
            return sign === -1 ? INT_MIN : INT_MAX;
        }

        result = result * 10 + digit;
        i++;
    }

    // Apply the sign to the result
    result *= sign;

    return result;
};

// Example usage:
console.log(myAtoi("42"));        // Output: 42
console.log(myAtoi("   -042"));   // Output: -42
console.log(myAtoi("1337c0d3"));  // Output: 1337
console.log(myAtoi("0-1"));       // Output: 0
console.log(myAtoi("words and 987"));  // Output: 0

Solution in Java:

Java
public class Solution {
    public int myAtoi(String s) {
        // Define constants for the 32-bit integer limits
        final int INT_MAX = Integer.MAX_VALUE;
        final int INT_MIN = Integer.MIN_VALUE;
        
        // Initialize index, sign, and result
        int i = 0;
        int n = s.length();
        int sign = 1;
        int result = 0;
        
        // Step 1: Skip leading whitespace
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        
        // Step 2: Check for the sign
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }
        
        // Step 3: Convert digits to integer
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            
            // Check for overflow and clamp the value if necessary
            if (result > (INT_MAX - digit) / 10) {
                return (sign == -1) ? INT_MIN : INT_MAX;
            }
            
            result = result * 10 + digit;
            i++;
        }
        
        // Apply the sign to the result
        result *= sign;
        
        return result;
    }

}

Solution in C#:

C#
public class Solution {
    public int MyAtoi(string s) {
        // Define constants for the 32-bit integer limits
        const int INT_MAX = 2147483647;  // 2^31 - 1
        const int INT_MIN = -2147483648; // -2^31
        
        // Initialize index, sign, and result
        int i = 0;
        int n = s.Length;
        int sign = 1;
        int result = 0;
        
        // Step 1: Skip leading whitespace
        while (i < n && s[i] == ' ') {
            i++;
        }
        
        // Step 2: Check for the sign
        if (i < n && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }
        
        // Step 3: Convert digits to integer
        while (i < n && char.IsDigit(s[i])) {
            int digit = s[i] - '0';
            
            // Check for overflow and clamp the value if necessary
            if (result > (INT_MAX - digit) / 10) {
                return (sign == -1) ? INT_MIN : INT_MAX;
            }
            
            result = result * 10 + digit;
            i++;
        }
        
        // Apply the sign to the result
        result *= sign;
        
        return result;
    }
    
    
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com