A simple solution in cpp


  • 74
    G

    The idea is pretty straightforward. A valid number is composed of the significand and the exponent (which is optional). As we go through the string, do the following things one by one:

    1. skip the leading whitespaces;
    2. check if the significand is valid. To do so, simply skip the leading sign and count the number of digits and the number of points. A valid significand has no more than one point and at least one digit.
    3. check if the exponent part is valid. We do this if the significand is followed by 'e'. Simply skip the leading sign and count the number of digits. A valid exponent contain at least one digit.
    4. skip the trailing whitespaces. We must reach the ending 0 if the string is a valid number.

    =======================================================

    bool isNumber(const char *s) 
    {
        int i = 0;
        
        // skip the whilespaces
        for(; s[i] == ' '; i++) {}
        
        // check the significand
        if(s[i] == '+' || s[i] == '-') i++; // skip the sign if exist
        
        int n_nm, n_pt;
        for(n_nm=0, n_pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i++)
            s[i] == '.' ? n_pt++:n_nm++;       
        if(n_pt>1 || n_nm<1) // no more than one point, at least one digit
            return false;
        
        // check the exponent if exist
        if(s[i] == 'e') {
            i++;
            if(s[i] == '+' || s[i] == '-') i++; // skip the sign
            
            int n_nm = 0;
            for(; s[i]>='0' && s[i]<='9'; i++, n_nm++) {}
            if(n_nm<1)
                return false;
        }
        
        // skip the trailing whitespaces
        for(; s[i] == ' '; i++) {}
        
        return s[i]==0;  // must reach the ending 0 of the string
    }

  • 0
    Q

    Is this a valid number in your code?
    1.e1
    There should be at least one number after the dot to be a number.
    1.2 :number
    .2 :number

    1. :not a number

  • 0
    G

    As far as I know, "1.e1" is a valid number in any programming language. "1." is a valid number, and ".1" is also a valid number.


  • 0
    Q

    Yes on this leetcode test case, 1. is considered as a number. But in real life to any one, it is not a correct number format. Nobody writes 1 as "1.".A precision decimal must be given,


  • 0
    G

    Well in real life no science or math textbooks would use 'e' for scientific notation. I think the criteria are largely based on those in programming languages except that suffix is not allowed. e.g. "1f" does not seem to be a valid number here but in c "1f" is a single precision floating point number.

    I have to say the requirements are not very clear in this problem.


  • 8
    R

    A java version with similar idea

    public class Solution {
        public boolean isNumber(String s) {
        	char[] c=s.trim().toCharArray();
    	
    	if (c.length==0) return false;
    	
    	int i=0,num=0;
    	if (c[i]=='+'||c[i]=='-') i++;
    	
    	for(;i<c.length&&(c[i]>='0'&&c[i]<='9');i++) num++;
    	if (i<c.length&&c[i]=='.')i++;
    	for(;i<c.length&&(c[i]>='0'&&c[i]<='9');i++) num++;
    	
    	if (num==0) return false;
    	
    	if (i==c.length) return true;
    	else if (i<c.length&&c[i]!='e') return false;
    	else i++;
    	
    	num=0;
    	if (i<c.length&&(c[i]=='+'||c[i]=='-')) i++;
    	
    	for(;i<c.length&&(c[i]>='0'&&c[i]<='9');i++) num++;
    	if (num==0) return false;
    	
    	if (i==c.length) return true;
    	else return false;
    }
    }

  • 0
    Y

    I guess maybe you can add boundary check in the second for loop termination condition so that s[i] will not go out of boundary.


  • 0
    G

    Actually it is not necessary. All the for loops will terminate automatically if s[i] is 0.


  • 0
    G

    Thanks. I guess what trim() does is to remove the leading and trailing whitespaces. It doesn't seem that c or cpp has a very powerful string library. Have to write everything from scratch.


  • 2
    Y

    Yes, that seems very simple. I came up with my java code after struggling a lot.

    public class Solution {
       public boolean isNumber(String s) {
           s=s.trim();
           int i=0;
           while(i<s.length()&&s.charAt(i)!='e') i++;
           if(i==0||i==s.length()-1) return false;
           if(i==s.length()) return valid(s,false);
           else return valid(s.substring(0,i),false)&&valid(s.substring(i+1),true);
       }
       public boolean valid(String s,boolean hasdot){
           if(s.length()==0) return false;
           if(s.charAt(0)=='+'||s.charAt(0)=='-') s=s.substring(1);
           if(s.length()==0||s.equals(".")) return false;
           for(int i=0;i<s.length();i++){
               if(s.charAt(i)=='.'){
                   if(hasdot) return false;
                   hasdot=true;
                   continue;
               }
               if(s.charAt(i)<'0'||s.charAt(i)>'9') return false;
           }
           return true;
       }
    }

  • 0
    Y

    I think my code is very easy to understand. The basic idea is to split "s" into two parts according to "e", then deal with each part. The idea comes from:http://leetcodenotes.wordpress.com/2013/11/23/leetcode-valid-number/


  • 0
    N

    By using the library function:
    s[i] == ' '; Can be replaced by isspace(s[i]);
    (s[i]<='9' && s[i]>='0'); Can be replaced by isdigit(s[i]);
    and, for readability,
    return s[i]==0; Can be replaced by return s[i] == '\0';


  • 1
    N

    By using the library function:
    s[i] == ' '; Can be replaced by isspace(s[i]);
    (s[i]<='9' && s[i]>='0'); Can be replaced by isdigit(s[i]);
    and, for readability,
    return s[i]==0; Can be replaced by return s[i] == '\0';


  • 2

    Hi, GuaGua. I have been very annoyed with the large number of special cases of this problem and have no idea of how to handle them systematically. Well, after reading your solution, this problem immediately becomes easy and the code becomes clear and clean. Thankyou for your sharing!

    I have rewritten the code in C++ as follows.

    class Solution { 
    public:
        bool isNumber(string s) {
            int i = 0, n = s.length();
            // Skip the leading spaces
            while (i < n && isspace(s[i])) i++;
            // Skip the sign
            if (s[i] == '+' || s[i] == '-') i++;
            // Check for the following significant parts
            int digits = 0, dots = 0;
            while (i < n && (isdigit(s[i]) || s[i] == '.')) { 
                if (isdigit(s[i])) digits++;
                else dots++;
                i++;
            }
            if (digits < 1 || dots > 1) return false;
            if (i == n) return true;
            // Check for the exponential parts
            if (s[i] == 'e') {
                i++;
                if (i == n) return false;
                if (s[i] == '+' || s[i] == '-') i++;
                digits = 0;
                while (i < n && (isdigit(s[i]))) {
                    digits++;
                    i++;
                }
                if (digits < 1) return false;
            }
            // Skip the trailing spaces
            while (i < n && isspace(s[i])) i++;
            return i == n;
        }
    };
    

  • 0

    Great code! Thanks for your sharing!


  • 0
    G

    I'm glad this helps! Truly like this site 'cause we can always learn from each other.


  • 3
    P

    What if there are several zeros beforen a non-zero digit? Is "0001234" a valid one?


  • 0

    really concise and clean solution ! Thanks !


  • 0
    N

    @jianchao.li.fighter Hi, don't we need to check (i == n) before skipping the sign ?? It is possible the string is just whitespace. Then we would index out of bound.Thanks so much


  • 0
    S

    gorgeous!crystally clear!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.