08 String to Integer (atoi)

Description

String to Integer (atoi) - LeetCode

First Thought

This problem is easy, just operate every digit.

Those detailed requirements are not interesting and pretty easy to cope with, so I will just skip them.

The only alert is about overflow. The way to cope with over flow is the same as the last question. 07 Integer Reverse if (ans > max10 || (ans == max10 && c - 48 > 7))

But the problem lies in the update process: ans = ans * 10 + c - 48, the head part ans * 10 + c might cause a overflow due to it is ans * 10 + c - 48 that will not overflow, so just use ans * 10 + (c - 48) instead.

Code

class Solution {
public:
    int myAtoi(string s) {
        int ans = 0;
        int pos = 0;
        int max10 = INT_MAX / 10;
        int start = 0;
        for (char c : s) {

            if (c >= 48 && c <= 57)
            {
                start = 1;
                if (ans > max10 || (ans == max10 && c - 48 > 7))
                {
                    if (pos >= 0)
                        return INT_MAX;
                    return INT_MIN;
                }
                ans = ans * 10 + c - 48;
            }
            else if (start == 0) {
                if (c == ' ') continue;

                else if (c == '-') {
                    pos = -1;
                    start = 1;
                }
                else if (c == '+') {
                    pos = 1;
                    start = 1;
                }
                else break;
            }
            else {
                break;
            }
        }
        if (pos >= 0)
            return ans;
        else
            return ans * -1;
    }
};

Complexity Analysis

Time Complexity

$O(log(x))$, There are about $log_{10}(x)$ digits in number x

or $O(n)$, whatever.

Space Complexity

$O(1)$