Leetcode: String to Integer (atoi)

Question

Solved this:

Implement atoi to convert a string to an integer.

Requirements for atoi:

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.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution:

Check if string is null first then empty, if either is true, return 0. Keep iterating through string until we hit the first non-empty space character.

From this position, we check if the first character is '+' or '-'. If so, we move the iterator by one step and note the sign in boolean isNegative.

From the current position, as long as the character is an integer, we add it to solution while checking for overflow each time we do so. We keep iterating through the string until we hit a non-integer character and return solution:

class Solution {
    boolean isNegative = false;
    int i = 0; // string iterator position

    public int myAtoi(String str) {
        int solution = 0;

        if (str == null || str.isEmpty()) {
            return 0;
        }
        while (i < str.length() && str.charAt(i) == ' ') {
            i++; // discard leading whitespace
        }
        checkSign(str);
        for (; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                int prev = solution; // keep solution from last iter to check for overflow
                solution = solution*10; // move number left one position
                solution = solution+(str.charAt(i)-'0'); // increase solution by curr integer
                if (isOverflow(prev, solution)) {
                    if (isNegative) {
                        return Integer.MIN_VALUE;
                    }
                    return Integer.MAX_VALUE;
                }
            } else {
                return signSolution(solution); // we've reached a non-integer character before end of string
            }
        }
        return signSolution(solution); // last character of string is an integer
    }

    boolean isOverflow(int prev, int curr) {
        // prev = value at last iteration
        // curr = value after current iteration
        if (curr/10 == prev) {
            return false;
        }
        return true;
    }

    void checkSign(String str) {
        if (str.charAt(i) == '+') {
            i++;
        } else if (str.charAt(i) == '-') {
            isNegative = true;
            i++;
        }
    }

    int signSolution(int solution) {
        if (isNegative) {
            return solution*-1;
        }
        return solution;
    } 
  }

Answer 1

Normally when parsing a String into an int, people expect it to be a static method

Having to create a class to do the computation is a bit bulky, and then you need to worry about synchronization (what happens if this class is shared across multiple threads?)

boolean isOverflow(int prev, int curr) {
    // prev = value at last iteration
    // curr = value after current iteration
    if (curr/10 == prev) {
        return false;
    }
    return true;
}

This method is already a great candidate to become static, it only relies on its two inputs to figure out if an overflow happened

boolean isNegative = false;
int i = 0; // string iterator position

void checkSign(String str) //uses i and isNegative

int signSolution(int solution) //uses isNegative

These are slightly more tricky, int signSolution(int solution) can just take another parameter: static int signSolution(int solution, boolean isNegative)

void checkSign(String str) would need to be included as part of the myAtoI method or be rewritten a bit

If we treat + as whitespace, then it would only need to worry about handling -

static boolean checkSign(String str, int i)
{
    return str.charAt(i) == '-';
}

And calls to checkSign(str); would instead be if(checkSign(str)) i++;

---

Be consistent. You're mixing for and while loops of similar structure

while (i < str.length() && str.charAt(i) == ' ')
    i++;
[...]
for (; i < str.length(); i++) {
    [...]
}

They can either both be for loops, or both be while loops, but mixing is unexpected

for(; i < str.length() && str.charAt(i) == ' '; i++);
[...]
for(; i < str.length(); i++)
{
    [...]
}

vs

while(i < str.length() && str.charAt(i) == ' ')
    i++;
[...]
while(i < str.length())
{
    [...]
    i++;
}

---

Checking "whitespace" currently only checks spaces

Instead of using str.charAt(i) == ' ', you can offload complicated functionality to another method (and be easier to change later)

static boolean isWhiteSpace(char c)
{
    return c == ' ';
}

Then if you'd like to include all whitespace (and + and mentioned above)

static boolean isWhiteSpace(char c)
{
    return Character.isWhitespace(c) || (c == '+');
}

---

Instances of if(bool) return true; else return false; are the same as just return bool;

if (curr/10 == prev) {
        return false;
}
return true;

Can be simplified to just

return curr / 10 != prev;

---

OptionalA:

Another way to check for overflow is to store the output as a long, and check if it overflows

public static int myAtoI(String str)
{
    long solution = 0;
    [...]
}

private static isOverflow(long num)
{
    return num == (int)num;
}

---

OptionalB:

Instead of adding the values and then flipping the result, you could subtract values if it's a negative number