Programming with Passion Algorithms, Mobile Development, Robotics

Tuesday, May 2, 2017

LeetCode (Algorithms#8) ‒ String to Integer (atoi)

Problem

Implement atoi to convert a string to an integer.

Note: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Solution

The solution clearly takes O(n) as you iterate through each character of the string. The general case of the algorithm is similar to that of Reverse Integer where the resulting number is shifted before adding each new digit. The tricky part is handling all cases, which is the only reason this code is more than 3 lines long.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 72.65%

public int myAtoi(String str) {
    long res = 0l;
    if (str != null && str.length() > 0) {
        long sign = 1l;
        boolean numFound = false;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (!numFound && c==32) continue;
            if (c<48 || c>57) {
                if ((c==45 || c==43) && !numFound) {
                    sign = (c==45?-1l:1l);
                    numFound = true;
                } else break;
            } else {
                numFound = true;
                res = res*10 + sign*((int)c-48);
                if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
                else if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            }
        }
    }
    return (int)res;
}

No comments:

Post a Comment