Stack Overflow Asked by Matt Draft on November 17, 2020

I am not sure how to word this problem so I will show you. This is using leetcode and I’m trying to create an atoi method.

```
public int myAtoi(String s) {
System.out.println(s.matches("^[^ -0123456789].*")); //this is the regex I am debugging
if(s.matches("^[^ -0123456789].*")){
return 0;
}
int solution = 0;
s = s.replaceAll("[^-0123456789.]","");
solution = 0;
boolean negative = false;
if(s.charAt(0) == '-'){
s = s.replaceAll("-","");
negative = true;
}
if(s.matches("^[0-9]?[.][0-9]+")){
s = s.substring(0, s.indexOf('.'));
System.out.println(s);
}
for(int i = s.length(); i > 0; i--){
solution = solution + (s.charAt(s.length() - i) - 48) * (int)Math.pow(10,i - 1);
}
if(negative) solution = solution * -1;
if(negative && solution > 0) return (int) Math.pow(-2,31);
if(!negative && solution < 0) return (int) Math.pow(2,31) - 1;
return solution;
}
```

here is the output section screenshot provided incase I have missed something there but a text description also exists.

When the input is "+-12" the output is supposed to be (int) 0. This is due to the requirement being that "if the string does not start with a number, a space, or a negative sign" we return 0.

The line of code whch is supposed to handle this starts at 4 and looks like

```
if(s.matches("^[^ -0123456789].*")){
return 0;
}
```

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

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 (`?`

).

- for instance,
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";
// }
```

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).

Answered by Emma on November 17, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP