Java regex not picking up "+"

• We don't really have to use regular expressions for solving this problem, because of the time complexity.

  • for instance, if(s.matches("^[0-9]?[.][0-9]+")){ does not run linearly, runs quadratically due to the lazy quantifier (?).

• We can just loop through once (order of N) and define some statements:

class Solution {
    public static final int myAtoi(
        String s
    ) {
        s = s.trim();
        char[] characters = s.toCharArray();
        int sign =  1;
        int index = 0;

        if (
            index < characters.length &&
            (characters[index] == '-' || characters[index] == '+')
        ) {
            if (characters[index] == '-') {
                sign = -1;
            }

            ++index;
        }

        int num = 0;
        int bound = Integer.MAX_VALUE / 10;

        while (
            index < characters.length &&
            characters[index] >= '0' &&
            characters[index] <= '9'
        ) {
            final int digit = characters[index] - '0';

            if (num > bound || (num == bound && digit > 7)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            num *= 10;
            num += digit;
            ++index;
        }

        return sign * num;

    }
}

• Here is a C++ version, if you might be interested:

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>


// The following block might trivially improve the exec time;
// Can be removed;
static const auto imporve_runtime = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();

#define MAX INT_MAX
#define MIN INT_MIN
using ValueType = std::int_fast32_t;

struct Solution {
    static const int myAtoi(
        const std::string str
    ) {
        const ValueType len = std::size(str);
        ValueType sign = 1;
        ValueType index = 0;

        while (index < len && str[index] == ' ') {
            index++;
        }

        if (index == len) {
            return 0;
        }

        if (str[index] == '-') {
            sign = -1;
            ++index;

        } else if (str[index] == '+') {
            ++index;
        }

        std::int_fast64_t num = 0;

        while (index < len && num < MAX && std::isdigit(str[index])) {
            ValueType digit = str[index] - '0';
            num *= 10;
            num += digit;
            index++;
        }

        if (num > MAX) {
            return sign == 1 ? MAX : MIN;
        }

        return sign * num;
    }
};

// int main() {
//     std::cout << Solution().myAtoi("words and 987") << "n";
//     std::cout << Solution().myAtoi("4193 with words") << "n";
//     std::cout << Solution().myAtoi("   -42") << "n";
// }

Regarding your question

I don't know what is wrong with my regex, can someone please help?

• If you'd like to see how a regular expression solution works, maybe this concise Python version would help (also runs on O(N ^ 2)):

import re

class Solution:
    def myAtoi(self, s: str) -> int:
        MAX, MIN = 2147483647, -2147483648
        DIGIT_PATTERN = re.compile(r'^s*[+-]?d+')
        s = re.findall(DIGIT_PATTERN, s)
        try:
            res = int(''.join(s))
        except:
            return 0
        if res > MAX:
            return MAX
        if res < MIN:
            return MIN
        return res

• We can workaround the expression of ^s*[+-]?d+ by dividing it into two subexpressions so that we would be able to get rid of the lazy quantifier and design an order of N solution, yet that would be unnecessary (and is also against the KISS principle).