String to Integer Problem and Solution

1. Introduction

The "String to Integer" (atoi) problem involves converting a string to a 32-bit signed integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

2. Solution in C++

#include <iostream>
#include <climits>
using namespace std;

int myAtoi(string str) {
    int sign = 1, base = 0, i = 0;
    while (str[i] == ' ') { i++; }
    if (str[i] == '-' || str[i] == '+') {
        sign = 1 - 2 * (str[i++] == '-');
    }
    while (str[i] >= '0' && str[i] <= '9') {
        if (base > INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
            return (sign == 1) ? INT_MAX : INT_MIN;
        }
        base = 10 * base + (str[i++] - '0');
    }
    return base * sign;
}

// Example usage
int main() {
    string s = "42";
    cout << "Converted: " << myAtoi(s) << endl;
    return 0;
}

Output:

Converted: 42

Explanation:

1. myAtoi function skips all whitespaces.

2. It checks for an optional sign ('+' or '-') and sets the sign variable accordingly.

3. It processes the string character by character, converting numerical characters to an integer.

4. The function checks for overflow and underflow conditions.

5. Returns the integer with the appropriate sign.

3. Solution in Java

public class StringToInteger {
    public static int myAtoi(String str) {
        int i = 0, sign = 1, base = 0;
        while (i < str.length() && str.charAt(i) == ' ') { i++; }
        if (i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            sign = (str.charAt(i++) == '-') ? -1 : 1;
        }
        while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            if (base > Integer.MAX_VALUE / 10 ||
                (base == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            base = 10 * base + (str.charAt(i++) - '0');
        }
        return base * sign;
    }

    // Example usage
    public static void main(String[] args) {
        String s = "42";
        System.out.println("Converted: " + myAtoi(s));
    }
}

Output:

Converted: 42

Explanation:

1. Similar to C++, myAtoi in Java skips whitespaces and checks for the sign.

2. It iterates through the string, converting characters into an integer, checking for overflow/underflow.

3. Returns the integer with the correct sign.

4. Solution in Python

def myAtoi(s):
    s = s.strip()
    if not s:
        return 0

    sign = -1 if s[0] == '-' else 1
    if s[0] in ['-', '+']:
        s = s[1:]

    result, i = 0, 0
    while i < len(s) and s[i].isdigit():
        if result > (2**31 - 1) // 10 or (result == (2**31 - 1) // 10 and int(s[i]) > 7):
            return 2**31 - 1 if sign == 1 else -2**31
        result = result * 10 + int(s[i])
        i += 1

    return result * sign

# Example usage
s = "42"
print("Converted:", myAtoi(s))

Output:

Converted: 42

Explanation:

1. myAtoi in Python strips the string of leading whitespaces.

2. It checks for a sign and processes the string to convert it into an integer.

3. Overflow and underflow conditions are checked using 32-bit integer limits.

4. Returns the integer with the applied sign.