Implement ATOI/STRSTR

Problem Overview

LeetCode Question: String to Integer (atoi)

This coding problem is a classic implementation task that involves parsing a string to convert it into an integer, similar to the C/C++ atoi function. You'll be tasked with writing a function to convert a string to a 32-bit signed integer (similar to how atoi() works in C/C++).

URL: String to Integer (atoi)

The function should account for whitespace, optional leading sign characters ('+' or '-'), and invalid characters, and it must handle integer overflow and underflow.

Understanding the Problem

To effectively solve this problem, we need to handle several aspects of string parsing:

1. Whitespace Handling: Skip any leading spaces or whitespace until a non-whitespace character is encountered.

2. Sign Handling: Check for a possible sign character ('+' or '-') for the integer.

3. Numeric Conversion: Iterate through the subsequent characters converting them to an integer until a non-numeric character is encountered.

4. Overflow Handling: If at any point the integer value goes beyond the limits of a 32-bit signed integer, return INT_MAX or INT_MIN.

5. Condition: If the string is empty or only contains spaces, or if the first non-whitespace character is non-numeric (and not a sign), return 0.

Key DSA Concepts and Theory

String Manipulation

String manipulation is foundational for this problem. We primarily work with string indexing and parsing numeric values character-by-character.

Integer Limits

In this problem, it is crucial to recognize the boundaries of a 32-bit signed integer, which are:

• INT_MIN = -2,147,483,648
• INT_MAX = 2,147,483,647

These limits are vital when handling overflow or underflow scenarios during conversion.

Solution Approach

We'll utilize a straightforward approach by implementing a manual string parser to handle conversion logic. Let's outline this step-by-step:

Steps with C++ Code

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

int myAtoi(string s) {
    int index = 0, sign = 1, result = 0;
    
    // Skip whitespace characters
    while (index < s.length() && s[index] == ' ') {
        ++index;
    }
    
    // Check for optional '+' or '-' sign
    if (index < s.length() && (s[index] == '-' || s[index] == '+')) {
        sign = (s[index] == '-') ? -1 : 1;
        ++index;
    }
    
    // Convert numbers and avoid overflow
    while (index < s.length() && s[index] >= '0' && s[index] <= '9') {
        int digit = s[index] - '0';
        
        // Check for overflow
        if ((result > INT_MAX / 10) || (result == INT_MAX / 10 && digit > INT_MAX % 10)) {
            return (sign == 1) ? INT_MAX : INT_MIN;
        }
        
        result = result * 10 + digit;
        ++index;
    }
    
    return result * sign;
}

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

Steps with Java Code

public class StringToIntegerAtoi {
    public int myAtoi(String s) {
        int index = 0, sign = 1, result = 0;
        
        // Skip whitespaces
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        
        // Handle sign
        if (index < s.length() && (s.charAt(index) == '-' || s.charAt(index) == '+')) {
            sign = (s.charAt(index) == '-') ? -1 : 1;
            index++;
        }
        
        // Convert number and check for overflow
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            int digit = s.charAt(index) - '0';
            
            // Check overflow
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            result = result * 10 + digit;
            index++;
        }
        
        return result * sign;
    }

    public static void main(String[] args) {
        StringToIntegerAtoi atoi = new StringToIntegerAtoi();
        String s = "   -42";
        System.out.println("Converted integer: " + atoi.myAtoi(s));
    }
}

Time and Space Complexity Analysis

• Time Complexity:

  • The algorithm runs in O(n) time complexity, where n is the length of the input string. This is because we potentially iterate through each character of the string once.

• Space Complexity:

  • O(1), since the solution requires a constant amount of space for variables regardless of the input size.

Common Mistakes to Avoid

• Not Handling Leading Spaces: Forgetting to skip initial whitespace can lead to incorrect results.
• Not Checking for Overflow Appropriately: Ensure that before multiplying result by 10 or adding a new digit, it does not cause overflow.
• Ignoring Non-Numeric Characters: Hardcoding or failing to correctly skip or terminate processing upon encountering non-numeric characters could lead to errors.

Similar Problems on LeetCode

• Valid Number (LC #65)
• Add Strings (LC #415)
• Basic Calculator II (LC #227)

Additional Resources and References

• Understanding the atoi() function in C
• String Manipulation Algorithms - GeeksforGeeks
• Java String Methods - Oracle Docs

This article aims to provide a thorough understanding of the conversion task, enabling an effective solution through nuanced handling of input constraints and string manipulation techniques.