Wednesday, October 8, 2014

Leetcode: Valid number

Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
Understand the problem:
To understand the problem, several questions need to ask for the interviewer?
Q: How to account for whitespaces in the string?
A: When deciding if a string is numeric, ignore both leading and trailing whitespaces.

Q: Should I ignore spaces in between numbers – such as “1 1”?
A: No, only ignore leading and trailing whitespaces. “1 1” is not numeric.

Q: If the string contains additional characters after a number, is it considered valid?
A: No. If the string contains any non-numeric characters (excluding whitespaces and decimal point), it is not numeric.

Q: Is it valid if a plus or minus sign appear before the number?
A: Yes. “+1” and “-1” are both numeric.

Q: Should I consider only numbers in decimal? How about numbers in other bases such as hexadecimal (0xFF)?
A: Only consider decimal numbers. “0xFF” is not numeric.

Q: Should I consider exponent such as “1e10” as numeric?
A: No. But feel free to work on the challenge that takes exponent into consideration. (The Online Judge problem does take exponent into account.)

Idea:
There are the flows to solve this question:
1. Skip the leading white spaces, if there is any.
2. Skip the + or - sign, if there is any.
3. Skip the first segment of numerical characters.
4. Skip the '.' character if there is any
5. Skip the second segment of numerical characters. e.g 12.14
6. If we consider the exponent character, e and E, skip that one if there is any
7. Skip the + or - sign
8. Skip the numerical characters followed by the E or e.
9. Remove trialing white spaces, if there is any
10. Check if we have reached the end of the string. If yes, return true. Else return false.


Code (Java):
public class Solution {
    public boolean isNumber(String s) {
        int i = 0;
        int n = s.length();
        
        // step 1: skip leading white spaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        
        // step 2: Skip + or - sign
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            i++;
        }
        
        boolean isNumeric = false;
        // step 3: skip the first segement of numeric characters
        while (i < n && Character.isDigit(s.charAt(i))) {
            i++;
            isNumeric = true;
        }
        
        // step 4 and 5 skip the . character and the following numeric characters, if any
        if (i < n && s.charAt(i) == '.') {
            i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
        
        // step 6 and 7 and 8, exponent character and following numeric characters
        if (isNumeric && i < n && (s.charAt(i) == 'e' || s.charAt(i) == 'E')) {
            i++;
            isNumeric = false;
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
                i++;
            }
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
        // step 9: Remove trailing white spaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        
        return isNumeric && i == n;
    }
}

2 comments:

  1. There should be check before line no 33 for the case 1.e10

    ReplyDelete
  2. isNumeric should be set to false for step 4 & 5 (line 25) to avoid the case failure of "3." as it's not a valid number.

    ReplyDelete