3
\$\begingroup\$

Problem: String to integer(leetcode)

Implement atoi which converts a string to an integer.

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.

Note:

  • Only the space character ' ' is considered as a whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [-2^31, 2^31-1]. If the numerical value is out of the range of representable values, (2^31-1) or -2^31 is returned.

My solution:

I have implemented this code below. I have noted down the requirements and implemented the code. It was hard to keep track of all the details. Before acceptance, I got WA 4 times(and it seems like the code I've written is not compact).

class Solution:
    def myAtoi(self, s: str) -> int:
            l = len(s)
            if l==0:
                print(1)
                return 0
            if l==1:
                if s==" " or s=="+" or s=="-":
                    return 0
                elif(s.isnumeric()):
                    return int(s)
                else:
                    return 0
            res = ""
            i = 0
            while(i<l and s[i]==" "):
                i+=1
                if i==l:
                    return 0
            ispos = False
            if(s[i]=="+"):
                ispos = True
                i+=1
            isnegative = False
            if(s[i]=='-' and not ispos):
                isnegative = True
                i+=1
            if(i<len(s) and not s[i].isnumeric() and s[i]!='+' and s[i]!='-'):
                return 0
            while(i<l):
                if s[i].isnumeric():
                    res += s[i]
                else:
                    break
                i+=1 
            if len(res)>0:
                x = int(res)
            else:
                return 0
            if isnegative:
                if x>=(1<<31):
                    return -(1<<31)
                x *= -1
            if x>=((1<<31) - 1):
                return (1<<31)-1
            return x

Can anyone write a compact code for this problem?


I also like to know if there is an approach to solve this kind of implementation problems so that I can write compact code. Can anyone share any better method to analyze this type of implementation problem? (or, any suggestion to be better in solving this kind of problems where we need to keep track of many things)

\$\endgroup\$
  • 3
    \$\begingroup\$ Could you include the problem statement in the question? Links can rot. \$\endgroup\$ – dfhwze Aug 7 at 8:43
11
\$\begingroup\$

Styling

Try to make the code follow the PEP 8 Style Guidelines, this will make your code follow the Python conventions, and also more readable. So do if l == 1 instead of if l==1, my_atoi instead of myAtoi, etc

Code structure

It seems that page requires the code to be inside a class. Leaving the exercise aside for a moment: You don't need that function inside a class, because you are never using anything of the class itself. It makes more sense to define that method outside the class, and without the (unused) self parameter.

Skiping whitespaces

while(i<l and s[i]==" "):
    i+=1
    if i==l:
        return 0
  1. You don't need those parenthesis on the while in Python.
  2. Your code might not detect some whitespace characters like \t (it seems the exercise accepts that though); use the method isspace().
  3. Instead of checking i == l on every iteration (when it could only happen in the last one), check it once you are out of the loop. This allows us to remove the special treatment to empty strings: if s is empty, it won't enter the loop and i == l, so it will return 0.
while i < l and s[i].isspace():
    i += 1

if i == l:
    return 0

Sign

Your code to handle the sign is too complicated. Instead of keeping ispos and isnegative, you could just keep a factor that is either 1 or -1. So instead of

ispos = False
if(s[i]=="+"):
    ispos = True
    i+=1
isnegative = False
if(s[i]=='-' and not ispos):
    isnegative = True
    i+=1

you can do

factor = -1 if s[i] == '-' else 1
# Skip the sign character if necessary
if s[i] == '-' or s[i] == '+':
    i += 1

Reading the number

if(i<len(s) and not s[i].isnumeric() and s[i]!='+' and s[i]!='-'):
    return 0
while(i<l):
    if s[i].isnumeric():
        res += s[i]
    else:
        break
    i+=1
  1. If we have already parsed the sign, why accept another sign again?

  2. Be careful, isnumeric() accepts things like ½, which you probably don't want; use isdigit() instead. EDIT: As noted in the comments, isdigit() will accept things like "¹". So it's probably better to just do s[i] in '0123456789'

  3. It's good practice (and helps avoid unexpected bugs) to declare variables the closest possible to where they are used. You declare res = "" at the beginning of your function, but haven't used it until now.

  4. The while and if can be condensed into a single, more compact loop:

res = ""
while i < l and s[i].isdigit():
    res += s[i]
    i += 1

# You can check if an string is empty doing this:
if not res:
    return 0

Arrived to this point, if the function hasn't returned, we know res contains a number. The way you handle the valid range, before applying the sign, is not very intuitive; it's better if you first apply the sign.

x = factor * int(res)
if x > (1 << 31):
    return (1<<31)
elif x < -((1 << 31) - 1):
    return (1 << 31) - 1
else:
    return x

Or it might be even better to clamp your number using min and max:

return max(-(1 << 31) + 1, min(1 << 31, factor * int(res)))

Final code

I have removed the special case of l == 1 because it is already handled by the rest of the code. This is my final code (untested):

def my_atoi(s: str) -> int:
    l = len(s)

    while i < l and s[i].isspace():
        i += 1

    if i == l:
        return 0

    factor = -1 if s[i] == '-' else 1
    # Skip the sign character if necessary
    if s[i] == '-' or s[i] == '+':
        i += 1

    res = ""
    while i < l and s[i].isdigit():
        res += s[i]
        i += 1

    if not res:
        return 0

    return max(-(1 << 31) + 1, min(1 << 31, factor * int(res)))
\$\endgroup\$
  • \$\begingroup\$ If the requirement really is to make the code "more compact", then perhaps it's reasonable to throw PEP-8 out of the window. But it does make us ask, "why is that a goal??".... \$\endgroup\$ – Toby Speight Aug 7 at 8:54
  • \$\begingroup\$ I thought he meant compact in less lines or less code. I cannot see any benefit of removing whitespaces when they make the code more readable. \$\endgroup\$ – eric.m Aug 7 at 9:10
  • 2
    \$\begingroup\$ Beware, though, even isdigit has its flaws. "¹".isdigit() returns True. The only way to be really sure I know of is to test x in set(string.digits) or similar. \$\endgroup\$ – Graipher Aug 7 at 14:01
  • 1
    \$\begingroup\$ @taritgoswami No, it is a unicode symbol, a 1 that is raised, to be used as an exponent,. It still counts as a digit to str,isdigit, but int("¹") fails with a ValueError. So using str.isdigit is not sufficient to reject values that are not parseable by int. Your only options are explicitly whitelisting only the ASCII digits (which is what string.digits contains), or by trying to parse a digit with int and skipping it if an exception is raised. \$\endgroup\$ – Graipher Aug 7 at 16:16
  • 5
    \$\begingroup\$ Would you also suggest a variable other than "l", given how similar it looks to "1" (if i == l, etc)? \$\endgroup\$ – Roberto Aug 7 at 17:10
4
\$\begingroup\$

You can also use strip() to remove whitespaces in strings. strip() will copy your string and remove both leading and trailing whitespaces.

foo_string = '    So much space for activities!     '
>>> foo_string.strip()
'So much space for activities!'

You can also use this to only remove leading whitespaces or trailing, using lstrip() and rstrip(), respectively.

You can then shorten your checks for valid operators by creating a string of valid operators and checking the first character. You can then check for operators in it.

>>> test_string = '-354'
>>> valid_operators = '+-'
>>> test_string[0] in valid_operators
True
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.