Leetcode P0065"Valid Number" 题解

博文中会简要介绍Leetcode P0065题目分析及解题思路。

“Valid Number”是一道比较考验细心和耐心的题目，这道题说白了就是在考察正则表达式。

Validate if a given string can be interpreted as a decimal number.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:

Numbers 0-9

Exponent - “e”

Positive/negative sign - “+”/”-“

Decimal point - “.”

Of course, the context of these characters also > matters in the input.

这道题的思路很直接明了，就是扫一遍根据各种flag判断就行。

需要特别注意的一点是，这道题中使用科学记数法，在指数e前的部分可以以小数点开头，所以这一部分只关心小数点个数和数字个数。后面部分则关心是否全部都是数字。这一思路在C++代码体现的比较明显，C++代码的写法相对更加精炼，是在Discussion上发现的，思路很清晰明了，可以提供参考。

以下是Java的题解代码实现。

class Solution {
    public boolean isNumber(String s) {
        if (s == null)
            return false;
        
        s = s.trim();
        boolean numSeen = false, numSeenAfterE = false, decimalPointSeen = false, eSeen = false;
        char[] chars = s.toCharArray();
        for (int itr=0; itr<chars.length; ++itr) {
            if (chars[itr] == '+' || chars[itr] == '-') {
                if (itr > 0 && chars[itr-1] != 'e')
                    return false;
            }
            else if (chars[itr] >= '0' && chars[itr] <= '9') {
                if (eSeen)
                    numSeenAfterE = true;
                else
                    numSeen = true;
            }
            else if (chars[itr] == '.') {
                if (decimalPointSeen || eSeen)
                    return false;
                
                decimalPointSeen = true;
            }
            else if (chars[itr] == 'e') {
                if (eSeen || !numSeen)
                    return false;
                
                eSeen = true;
            }
            else 
                return false;
        }
        
        return (eSeen? numSeen && numSeenAfterE: numSeen);
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool isNumber(string s) {
        if (s.empty())
            return false;
        
        // Trim
        s.erase(0, s.find_first_not_of(" "));
        s.erase(s.find_last_not_of(" ")+1);
        
        int i = 0;
        // check the sign
        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; 
        
        // no more than one point, at least one digit
        if (n_pt > 1 || n_nm < 1) 
            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;
        }

        return s[i] == '\0';  // must reach the ending 0 of the string
    }
};

聖地亞歌

Leetcode P0065"Valid Number" 题解

Search

Table of Contents