Algorithm Day104 - String to Integer

Posted on In , Views:

🧩 Problem Description

LeetCode 8 - String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm follows these steps:

  1. Read and ignore leading whitespaces.
  2. Check if the next character is + or - (determine the sign).
  3. Read digits until a non-digit character or end of string.
  4. Clamp the result within the 32-bit integer range.

Example:

1
2
3
4
5
6
7
8
Input: s = "42"
Output: 42

Input: s = "   -42"
Output: -42

Input: s = "4193 with words"
Output: 4193

💡 First Thought (Use Built-in Functions)

One might think of using Integer.parseInt() or similar methods,
but those cannot handle invalid formats and overflow gracefully.
We need to implement the parsing logic manually.

⚙️ Optimized Approach — Manual Parsing

We manually iterate through the string, handle spaces, sign, digits, and overflow.

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == ' ') i++; // skip spaces

        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }

        int result = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            if (result > (Integer.MAX_VALUE - digit) / 10)
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            result = result * 10 + digit;
            i++;
        }

        return result * sign;
    }
}

⏱️ Complexity Analysis

Operation Time Complexity Space Complexity
Parse string O(n) O(1)

🧠 Key Takeaways

  • Manual parsing ensures robust handling of edge cases (overflow, invalid input).
  • Remember to check integer boundaries before multiplication.
  • Similar to C’s atoi() but safer for modern applications.

📘 Next Step: We’ll continue exploring string-to-number conversion problems next.