Leetcode: Valid Number

By | 2018 年 7 月 10 日

Question

Validate if a given string is numeric.

Some examples:
“0” => true
” 0.1 ” => true
“abc” => false
“1 a” => false
“2e10” => true

Analyze

This is a simple question, but there are too many uncertainties. Before start, should check with interviewer to make them clear. Although there are several examples in the description, but still missed some valid number examples in the test case, e.g. ‘.2’, ‘2.’.

Solution is quite simple, just scan from the beginning to the end, to consume some characters to keep it as valid number. And in the end verify if nothing left.

For example, in the beginning, space ' ' is allowed, so we can skip them if any; Then we may encounter '+' or '-'; And potentially an integer number, then if there is floating point '.', should either has number in the left or in the right, … etc.

Solutions

C, 100%

bool isRawNumber(char c) {
    return c >= '0' && c <= '9';
}

bool isInteger(char** ps) {
    int len = 0;
    while(**ps != '\0') {
        if(!isRawNumber(**ps)) break;
        ++len;
        ++(*ps);
    }
    return len > 0;
}

bool isNumber(char* s) {
    if(s == NULL) return false;
    //skip heading space
    while(*s == ' ') ++s;
    //check sign
    if(*s == '+' || *s == '-') ++s;
    //check first segment of number
    bool majorNumber = isInteger(&s);
    //check floating point
    if(*s == '.') {
        ++s;
        //then check number
        bool minorNumber = isInteger(&s);
        if(!minorNumber && !majorNumber) return false;
    } else {
        if(!majorNumber) return false;
    }
    //check scientific representation
    if(*s == 'e' || *s == 'E'){
        ++s;
        //check sign
        if(*s == '+' || *s == '-') ++s;
        //then check number
        if(!isInteger(&s)) return false;
    }
    //skip trailing space
    while(*s == ' ') ++s;
    //checking tail
    return *s == NULL;
}

Ruby

# @param {String} s
# @return {Boolean}
def is_number(s)
    return false if s.nil?
    idx = 0

    # skip heading spaces
    idx = skip_spaces(s, idx)

    # check sign
    idx, _ = check_sign(s, idx)

    # check major integer before floating point or e
    idx, major_len = check_integer(s, idx)

    # check floating point
    if idx < s.size && s[idx] == '.'
        idx += 1
        idx, minor_len = check_integer(s, idx)
        return false if minor_len == 0 && major_len == 0
    else
        # anyway we need a major or minor number present
        return false if major_len == 0
    end

    # check E
    if idx < s.size && %w(e E).include?(s[idx])
        idx += 1
        idx, _ = check_sign(s, idx)
        idx, exp_len = check_integer(s, idx)
        return false if exp_len == 0
    end

    # skip trailing spaces
    idx = skip_spaces(s, idx)

    return idx == s.size
end

def check_sign(s, idx)
    sign = 1
    if idx < s.size
        if %w(+ -).include?(s[idx])
            sign = -1 if s[idx] == '-'
            idx += 1
        end
    end
    return [idx, sign]
end

def skip_spaces(s, idx)
    while idx < s.size && s[idx] == ' '
        idx += 1
    end
    return idx
end

def check_integer(s, idx)
    len = 0
    while idx < s.size && s[idx] >= '0' && s[idx] <= '9'
        len += 1
        idx += 1
    end
    return [idx, len]
end

C++

class Solution {
public:
    bool isNumber(string s) {
        int idx = 0;
        skipSpaces(s, idx);
        checkSign(s, idx);
        bool hasMajorNumber = isInteger(s, idx);
        cout << idx;
        if(idx < s.length() && s[idx] == '.') {
            ++idx;
            bool hasMinorNumber = isInteger(s, idx);
            if(!hasMajorNumber && !hasMinorNumber) {
                return false;
            }   
        } else if(!hasMajorNumber) {
            return false;
        }
        if(idx < s.length() && (s[idx] == 'e' || s[idx] == 'E')) {
            ++idx;
            checkSign(s, idx);
            if(!isInteger(s, idx)) {
                return false;
            }
        }
        skipSpaces(s, idx);
        return idx == s.length();
    }

private:
    bool isInteger(string s, int& idx) {
        int integerLen = 0;
        while(idx < s.length() && s[idx] >= '0' && s[idx] <= '9') {
            ++idx;
            ++integerLen;
        }
        return integerLen > 0;
    }

    void skipSpaces(string s, int& idx) {
        while(idx < s.length() && s[idx] == ' ') {
            ++idx;
        }
    }

    int checkSign(string s, int& idx) {
        int sign = 1;
        if(idx < s.length() && (s[idx] == '+' || s[idx] == '-')) {
            if(s[idx] == '-') sign = -1;
            ++idx;
        }
        return sign;
    }
};

Java 100%

class Solution {
    class NumberParser {
        private int idx = 0;
        private String s;

        public NumberParser(String s) {
            this.s = s;
        }

        public boolean isNumber() {
            skipSpaces();
            checkSign();
            boolean hasMajorNumber = isInteger();
            if(idx < s.length() && '.' == s.charAt(idx)) {
                ++idx;
                boolean hasMinorNumber = isInteger();
                if(!hasMajorNumber && !hasMinorNumber) {
                    return false;
                }
            } else if(!hasMajorNumber) {
                return false;
            }
            if(idx < s.length() && ('e' == s.charAt(idx) || 'E' == s.charAt(idx))) {
                ++idx;
                checkSign();
                if(!isInteger()) {
                    return false;
                }
            }
            skipSpaces();
            return idx == s.length();
        }

        private void skipSpaces() {
            while(idx < s.length() && ' ' == s.charAt(idx)) {
                ++idx;
            }
        }

        private void checkSign() {
            if(idx < s.length() && ('+' == s.charAt(idx) || '-' == s.charAt(idx)))
                ++idx;
        }

        private boolean isInteger() {
            int integerLen = 0;
            while(idx < s.length() && s.charAt(idx) >= '0' && s.charAt(idx) <= '9') {
                ++idx;
                ++integerLen;
            }
            return integerLen > 0;
        }
    }

    public boolean isNumber(String s) {
        return new NumberParser(s).isNumber();
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注