65. Valid Number

问题

Validate if a given string is numeric.

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

例子

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

分析

题目不难，但是要考虑各种情况：

• 可以分成整数、有符号整数（+/整数）、小数（有符号整数.整数）、科学计数法（小数e整数）四种类型；
• 数字字符串的首尾可以有任意多空格和0；
• 整数部分的字符只能是[0-9].

不难发现，我们可以把数字字符串拆解成四种类型中的若干种，然后判断拆解后的简单类型就行了。例如 +1.023e100 ，就可以拆解成+1.023和100，+1.023再可以拆解成+1和023。到最后都被拆至整数，然后就好判断了。

要点

拆解法，将复杂问题分解成若干简单问题。

时间复杂度

O(n)，n为数字字符串的长度。

空间复杂度

O(1)

代码

class Solution {
public:
    bool isNumber(string s) {
        trim(s); // 去除首尾空格
        removeSign(s); // 去除符号位
        size_t ePos = s.find('e');
        if (ePos == string::npos) 
            return isDecimal(s); // 不是科学计数，直接判断是不是小数
        else {
            string front = s.substr(0, ePos);
            string back = s.substr(ePos + 1);
            // 判断e前后两部分分别是不是小数和整数
            return isDecimal(removeSign(front)) && isInteger(removeSign(back));
        }
    }
    
private:
   // 是不是小数
   bool isDecimal(const string &s) {
        size_t dotPos = s.find('.');
        if (dotPos == string::npos)
            return isInteger(s);
        string front = s.substr(0, dotPos);
        string back = s.substr(dotPos + 1);
        if (front.empty() && back.empty()) 
            return false;
        if ((front.empty() || isInteger(front)) && 
            (back.empty() || isInteger(back)))
            return true;
        return false;
    }
    
    // 是不是整数
    bool isInteger(const string &s) {
        if (s.empty()) return false;
        for (char c : s)
            if (c < '0' || c > '9')
                return false;
        return true;
    }
    
    // 去除首尾空格
    void trim(std::string &s) {  
        if (s.empty()) return;
        s.erase(0, s.find_first_not_of(' '));
        s.erase(s.find_last_not_of(' ') + 1);
    }
    
    // 去除符号位
    std::string &removeSign(std::string &s) {
        if (s.empty()) return s;
        if (s[0] == '+' || s[0] == '-')
            s.erase(0, 1);
        return s;
    }
};